给出长度为n的数组,求能否从中选出若干个,使他们的和为K.如果可以,输出:Yes,否则输出No Input 输入数据为多组,每组两行。 第一行:输入N,K,为数组的长度和需要判断的和(2<=N<=20,1<=K<=10^9),请你帮我打一下这个代码用c语言
时间: 2024-06-06 16:10:51 浏览: 118
我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k 第二行输入n个整数(c1 c2
#include <stdio.h>
int arr[20]; // 存储输入的数组
int n, k; // 数组的长度和需要判断的和
// 递归函数,判断是否能从数组中选出一些数使它们的和为sum
int dfs(int sum, int index) {
// 如果sum等于k,表示已经选出一些数使它们的和为k,可以结束递归
if (sum == k) {
return 1;
}
// 如果已经到达数组的末尾或者sum已经大于k,表示无法选出一些数使它们的和为k,结束递归
if (index >= n || sum > k) {
return 0;
}
// 选或不选当前这个数,两种情况都要判断
return dfs(sum + arr[index], index + 1) || dfs(sum, index + 1);
}
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// 调用递归函数判断是否能从数组中选出一些数使它们的和为k
if (dfs(0, 0)) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
阅读全文