整数"/>
[深度优先搜索DFS]找出一组数是否能凑成一个整数
n=4
a={1,2,4,7}
k=13
输出Yes
n=4
a={1,2,4,7}
k=15
输出No#include <iostream>using namespace std;int a[10]; int n; int k;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,就返回falsereturn false; }void solve() {if (dfs(0, 0)){cout << "Yes" << endl;}else{cout << "No" << endl;} }int main() {cin >> n;int i;for (i = 0; i < n; ++i){cin >> a[i];}cin >> k;solve();return 0; }
更多推荐
[深度优先搜索DFS]找出一组数是否能凑成一个整数
发布评论