给出长度为n的数组,求能否从中选出若干个,使他们的和为K.如果可以,输出:Yes,否则输出No Input 输入数据为多组,每组两行。 第一行:输入N,K,为数组的长度和需要判断的和(2<=N<=20,1<=K<=10^9),请你帮我打一下这个代码用c语言
时间: 2024-05-20 09:16:27 浏览: 24
算法/编程练习:找出若干个数使其和最接近于M
#include <stdio.h>
int nums[20]; // 存储输入的数组
int n, k; // 数组长度和需要判断的和
int dfs(int cur, int sum) { // cur为当前考虑到的下标,sum为当前已经累加的和
if (sum == k) { // 如果当前和已经等于需要的和,那么就找到了一组解
return 1; // 返回1表示找到了解
}
if (cur >= n || sum > k) { // 如果当前下标已经超过了数组长度或者当前和已经大于需要的和,那么就无解
return 0; // 返回0表示无解
}
if (dfs(cur + 1, sum + nums[cur])) { // 如果选择当前下标对应的数,能找到一组解
return 1; // 返回1表示找到了解
}
if (dfs(cur + 1, sum)) { // 如果不选择当前下标对应的数,能找到一组解
return 1; // 返回1表示找到了解
}
return 0; // 返回0表示无解
}
int main() {
while (scanf("%d%d", &n, &k) == 2) { // 多组数据
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]); // 输入数组
}
if (dfs(0, 0)) { // 从下标0开始,当前和为0开始dfs
printf("Yes\n"); // 找到了解,输出Yes
} else {
printf("No\n"); // 没有找到解,输出No
}
}
return 0;
}
阅读全文