深度優先搜索的用法——求數組部分和 · 算法程序設計

**深度優先搜索的用法——求數組部分和** <table border="1" cellspacing="0" cellpadding="0" width="80%"><tbody><tr><td valign="top">問題主題：求數組部分和</td></tr><tr><td valign="top">問題描述：給定整數a1,a2, … an，判斷能否從中選出若干個數，使得它們的和為k。限制條件：1<=n<=20-108<=ai<=108-108<=k<=108</td></tr><tr><td valign="top">樣例：輸入n=4a={1,2,4,7}k=13輸出Yes (13=2+4+7)輸入n=4a={1,2,4,7}k=15輸出????No</td></tr></tbody></table> ### 【解法一】 ### 解題分析： ???用遞歸的方法實現深度優先搜索，從a0開始依次判斷，決定ai加入或不加入，對每一個種組合進行判斷，決定是否存在和為k的情況。 ### 程序實現: **C++** <table border="1" cellspacing="0" cellpadding="0" width="80%"><tbody><tr><td valign="top">#include?"stdafx.h"#include?"iostream"?using?namespace?std;?const?int?MAX = 10;int?????result;int?a[MAX];int?sum = 0;?bool?resolve(int?a[],?int?n,?int?i,?int?sum) ;?int?_tmain(int?argc, _TCHAR*?argv[]) {?????????int?n;?????????cout?<<?"請?輸o?入¨?n和¨a結¨￠果?的ì?大?¨?小?:"?<<endl;?????????cin?>> n >> result;?????????cout?<<?"請?輸o?入¨?n個?數oy:"?<<endl;?????????for(int?i=0;?i<n;?i++) {???????????????????cin?>> a[i];?????????}?????????if(resolve(a, n, 0, sum))???????????????????cout?<<?"Yes"?<<endl;?????????else???????????????????cout?<<?"No"?<<?endl;?????????return?0;}?bool?resolve(int?a[],?int?n,?int?i,?int?sum) {?????????if(i?>= n)???????????????????return?sum == result;?????????//不?選?a[i]?????????if(resolve(a, n, i+1, sum))???????????????????return?true;?????????//加¨?上|?a[i]?????????if(resolve(a, n, i+1,?sum+a[i]))???????????????????return?true;?????????return?false;}?</td></tr></tbody></table> **Java** <table border="1" cellspacing="0" cellpadding="0" width="80%"><tbody><tr><td valign="top"><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> </td></tr></tbody></table> **** ### 算法復雜度： ???時間復雜度O(2n)