部分和问题

这是程序设计中的一类经典问题，题目如下：

部分和问题
给定整数 a 1 、a 2 、…、a n ，判断是否可以从中选出若干数，使它们的和恰好为 k。

限制条件
1 ≤ n ≤ 20
-10^8 ≤ a i ≤ 10^8
-10^8 ≤ k ≤ 10^8

样例一
输入
n=4
a={1,2,4,7}
k=13
输出
Yes (13 = 2 + 4 + 7)
样例二
输入
n=4
a={1,2,4,7}
k=15
输出
No

#include <stdio.h>
#define MAX_N 100000 //宏定义后无分号
// 输入
int a[MAX_N];
int n, k;
// 已经从前i项得到了和sum，然后对于i项之后的进行分支
bool dfs(int i, int sum)
{
// 如果前n项都计算过了，则返回sum是否与k相等
if (i == n) return sum == k;
// 不加上a[i]的情况
if (dfs(i + 1, sum)) return true;
// 加上a[i]的情况
if (dfs(i + 1, sum + a[i])) return true;
// 无论是否加上a[i]都不能凑成k就返回false
return false;
}
void solve()
{
if (dfs(0, 0)) printf("Yesn");
else printf("Non");
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
scanf("%d", &k);
solve();
return 0;
}

最后

以上就是苹果大船为你收集整理的部分和问题的全部内容，希望文章能够帮你解决部分和问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。