部分和问题 代码(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
?
?
?
?
?
?
?