[深度优先搜索DFS]找出一组数是否能凑成一个整数

整数"/>

[深度优先搜索DFS]找出一组数是否能凑成一个整数

n=4

a={1,2,4,7}

k=13

输出Yes

n=4

a={1,2,4,7}

k=15

#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;
}