部分和问题（简单版）

正式开始学习dfs的用法，突然发现以前不能做的问题原来是深度优先问题；

练手题很简单，大概意思就是在就是一系列数中是否能找出几个数相加，使结果等于一个给定的数

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 int a[100] = { 1,2,4,7 }, n = 4, k=11;
 5 bool dfs(int i, int sum)
 6 {
 7     if (i == n) return sum == k;
 8     if (dfs(i + 1, sum)) return true;
 9     if (dfs(i + 1, sum+a[i])) return true;
10     return false;
11 }
12 void solve()
13 {
14     if (dfs(0, 0)) cout << "Yes" << endl;
15     else cout << "No" << endl;
16 }
17 int main()
18 {
19     solve();
20     return 0;
21 }

循环结束的条件是i==n，即前n项都计算完成后，判断是否等于sum，

改良升级版（规定几个数相加，使的结果等于给定的一个数）

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 int a[100] = { 1,2,4,7 }, n = 4, k=11;
 5 bool dfs(int i, int sum,int mark)
 6 {
 7     if (i == n&&mark==2) return sum == k;
 8     if (i == n && mark != 2) return false;
 9     if (dfs(i + 1, sum,mark)) return true;
10     if (dfs(i + 1, sum+a[i],mark+1)) return true;
11     return false;
12 }
13 void solve()
14 {
15     if (dfs(0, 0,0)) cout << "Yes" << endl;
16     else cout << "No" << endl;
17 }
18 int main()
19 {
20     solve();
21     return 0;
22 }