编程算法 - 部分和问题 代码(C)

部分和问题 代码(C)

?

题目: 给定整数a1, a2, ..., an, 判断是否可以从中选出若干数, 使它们的和恰好为k.

?

解法很多, 最简单的解法是使用深度优先搜索, 时间复杂度O(2^n), 不是最优解法.

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.7.13
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   

bool dfs (int i, int sum, int* a, int n, int k) {
	if (i==n) return sum == k;
	if(dfs(i+1, sum, a, n, k)) return true;
	if(dfs(i+1, sum+a[i], a, n, k)) return true;
	return false;
}

void solve(int* a, int n, int k) {
	if (dfs(0,0,a,n,k)) printf(Yes
);
	else printf(No
);
}


int main(void)
{
	const int MAX_N = 20;
	int a[MAX_N] = {1, 2, 4, 7};
	int n = 4, k = 13; //k位需要找到的数字

	solve(a, n, k);

    return 0;
}



  

?

?

Yes

?

?

?

?

?

?

?