深度优先搜索的用法——求数组部分和-算法程序设计

深度优先搜索的用法——求数组部分和

问题主题：求数组部分和

问题描述：

给定整数a1,a2, … an，判断能否从中选出若干个数，使得它们的和为k。

限制条件：

1<=n<=20

-10⁸<=a_i<=10⁸

-10⁸<=k<=10⁸

样例：

输入

n=4

a={1,2,4,7}

k=13

输出

Yes (13=2+4+7)

输入

n=4

a={1,2,4,7}

k=15

输出

【解法一】

解题分析：

用递归的方法实现深度优先搜索，从a0开始依次判断，决定ai加入或不加入，对每一个种组合进行判断，决定是否存在和为k的情况。

程序实现:

C++

#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 << "请?输º?入¨?n和¨ª结¨¢果?的Ì?大ä¨®小?:" <<endl;

cin >> n >> result;

cout << "请?输º?入¨?n个?数ºy:" <<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;

}

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 &gt;= 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();
}

}<br/><br/><p/>

算法复杂度：

时间复杂度O(2n)