**深度优先搜索的用法——求数组部分和**
<table border="1" cellspacing="0" cellpadding="0" width="80%"><tbody><tr><td valign="top"><p><strong>问题主题：</strong>求数组部分和</p></td></tr><tr><td valign="top"><p><strong>问题描述：</strong></p><p>给定整数a1,a2, … an，判断能否从中选出若干个数，使得它们的和为k。</p><p><strong>限制条件：</strong></p><p>1<=n<=20</p><p>-10<sup>8</sup><=a<sub>i</sub><=10<sup>8</sup></p><p>-10<sup>8</sup><=k<=10<sup>8</sup></p></td></tr><tr><td valign="top"><p><strong>样例：</strong></p><p>输入</p><p>n=4</p><p>a={1,2,4,7}</p><p>k=13</p><p>输出</p><p>Yes (13=2+4+7)</p><p>输入</p><p>n=4</p><p>a={1,2,4,7}</p><p>k=15</p><p>输出</p><p> No</p></td></tr></tbody></table>
### 【解法一】
### 解题分析：
用递归的方法实现深度优先搜索，从a0开始依次判断，决定ai加入或不加入，对每一个种组合进行判断，决定是否存在和为k的情况。
### 程序实现:
**C++**
<table border="1" cellspacing="0" cellpadding="0" width="80%"><tbody><tr><td valign="top"><p align="left"><span style="color:blue">#include</span> <span style="color:rgb(163,21,21)">"stdafx.h</span>"</p><p align="left"><span style="color:blue">#include</span> <span style="color:rgb(163,21,21)">"iostream</span>"</p><p align="left"> </p><p align="left"><span style="color:blue">using</span> <span style="color:blue">namespace</span> std;</p><p align="left"> </p><p align="left"><span style="color:blue">const</span> <span style="color:blue">int</span> MAX = 10;</p><p align="left"><span style="color:blue">int</span> result;</p><p align="left"><span style="color:blue">int</span> a[MAX];</p><p align="left"><span style="color:blue">int</span> sum = 0;</p><p align="left"> </p><p align="left"><span style="color:blue">bool</span> resolve(<span style="color:blue">int</span> a[], <span style="color:blue">int</span> n, <span style="color:blue">int</span> i, <span style="color:blue">int</span> sum) ;</p><p align="left"> </p><p align="left"><span style="color:blue">int</span> _tmain(<span style="color:blue">int</span> argc, _TCHAR* argv[]) {</p><p align="left"> <span style="color:blue">int</span> n;</p><p align="left"> cout << <span style="color:rgb(163,21,21)">"</span><span style="color:rgb(163,21,21)">请</span><span style="color:rgb(163,21,21)">?</span><span style="color:rgb(163,21,21)">输</span><span style="color:rgb(163,21,21)">º?</span><span style="color:rgb(163,21,21)">入</span><span style="color:rgb(163,21,21)">¨?n</span><span style="color:rgb(163,21,21)">和</span><span style="color:rgb(163,21,21)">¨ª</span><span style="color:rgb(163,21,21)">结</span><span style="color:rgb(163,21,21)">¨¢</span><span style="color:rgb(163,21,21)">果</span><span style="color:rgb(163,21,21)">?</span><span style="color:rgb(163,21,21)">的</span><span style="color:rgb(163,21,21)">Ì?</span><span style="color:rgb(163,21,21)">大</span><span style="color:rgb(163,21,21)">䨮</span><span style="color:rgb(163,21,21)">小</span><span style="color:rgb(163,21,21)">?:"</span> <<endl;</p><p align="left"> cin >> n >> result;</p><p align="left"> cout << <span style="color:rgb(163,21,21)">"</span><span style="color:rgb(163,21,21)">请</span><span style="color:rgb(163,21,21)">?</span><span style="color:rgb(163,21,21)">输</span><span style="color:rgb(163,21,21)">º?</span><span style="color:rgb(163,21,21)">入</span><span style="color:rgb(163,21,21)">¨?n</span><span style="color:rgb(163,21,21)">个</span><span style="color:rgb(163,21,21)">?</span><span style="color:rgb(163,21,21)">数</span><span style="color:rgb(163,21,21)">ºy:"</span> <<endl;</p><p align="left"> <span style="color:blue">for</span>(<span style="color:blue">int</span> i=0; i<n; i++) {</p><p align="left"> cin >> a[i];</p><p align="left"> }</p><p align="left"> <span style="color:blue">if</span>(resolve(a, n, 0, sum))</p><p align="left"> cout << <span style="color:rgb(163,21,21)">"Yes"</span> <<endl;</p><p align="left"> <span style="color:blue">else</span></p><p align="left"> cout << <span style="color:rgb(163,21,21)">"No"</span> << endl;</p><p align="left"> <span style="color:blue">return</span> 0;</p><p align="left">}</p><p align="left"> </p><p align="left"><span style="color:blue">bool</span> resolve(<span style="color:blue">int</span> a[], <span style="color:blue">int</span> n, <span style="color:blue">int</span> i, <span style="color:blue">int</span> sum) {</p><p align="left"> <span style="color:blue">if</span>(i >= n)</p><p align="left"> <span style="color:blue">return</span> sum == result;</p><p align="left"> <span style="color:green">//</span><span style="color:green">不</span><span style="color:green">?</span><span style="color:green">选</span><span style="color:green">?a[i</span>]</p><p align="left"> <span style="color:blue">if</span>(resolve(a, n, i+1, sum))</p><p align="left"> <span style="color:blue">return</span> <span style="color:blue">true</span>;</p><p align="left"> <span style="color:green">//</span><span style="color:green">加</span><span style="color:green">¨®</span><span style="color:green">上</span><span style="color:green">¦?a[i</span>]</p><p align="left"> <span style="color:blue">if</span>(resolve(a, n, i+1, sum+a[i]))</p><p align="left"> <span style="color:blue">return</span> <span style="color:blue">true</span>;</p><p align="left"> <span style="color:blue">return</span> <span style="color:blue">false</span>;</p><p align="left">}</p><p> </p></td></tr></tbody></table>
**Java**
<table border="1" cellspacing="0" cellpadding="0" width="80%"><tbody><tr><td valign="top"><p/><pre code_snippet_id="142845" snippet_file_name="blog_20140105_1_6613798" name="code" class="java">/**
* User: luoweifu
* Date: 14-1-7
* Time: 上午11:33
*/
public class PartSum {
private int array[];
private int result;
public PartSum() {
}
public PartSum(int[] array, int result) {
this.array = array;
this.result = result;
}
public void setArray(int[] array) {
this.array = array;
}
public void setResult(int result) {
this.result = result;
}
public boolean resolve(int[] array, int i, int sum) {
int n = array.length;
if(i >= n)
return sum == result;
if(resolve(array, i+1, sum))
return true;
if(resolve(array, i+1, sum+array[i]))
return true;
return false;
}
public void partsumResolve() {
if(resolve(array, 0, 0))
System.out.println("Yes");
else
System.out.println("No");
}
public static void main(String args[]) {
PartSum partSum = new PartSum(new int[]{1,2,4,7}, 13);
partSum.partsumResolve();
partSum.setResult(15);
partSum.partsumResolve();
}
}</pre><br/><br/><p/></td></tr></tbody></table>
****
### 算法复杂度：
时间复杂度O(2n)
