首页 > 代码库 > 部分和问题 (DFS)
部分和问题 (DFS)
来源:《挑战程序设计竞赛》
题目描述:
给定整数n个,判断是否能从中选出若干数,使它们的和恰好为k。
输入 n,k,array[0~n-1];
输出 Yes或者No。
思路:
从a1开始按顺序决定每个数加还是不加,在全部n个数都决定后在判断它们的和是不是k即可。
每个点都分出两种状态:加上当前数或者不加,dfs函数里主要完成:{状态的两种延伸(加上当前行数或者不加);当前状态的描述(判断当前和是否为k);}
代码:
#include <iostream> #include <cstring> #define MAXN 101 #define fooor(a,b) for(int i=a;i<b;i++) using namespace std; int ar[MAXN]; int n, k; bool dfs(int i, int sum) { if (i == n) return sum == k; if (dfs(i + 1, sum)) return true; if (dfs(i + 1, sum + ar[i])) return true; return false; } int main() { ios::sync_with_stdio(false); cin.tie(false); while (cin >> n >> k) { memset(ar, 0, sizeof(int)); fooor(0, n) { cin >> ar[i]; } cout << (dfs(0, 0) ? "Yes" : "No") << ‘\n‘; } return 0; }
部分和问题 (DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。