部分和问题（穷竭搜索）

问题描述：

　　给定整数a1、a2、......、an，判断是否可以从中选出若干数，使它们的和恰好为k。

限制条件：

　　　　1 <= n <= 20

　　　　-100000000 <= ai <= 100000000

　　　　-100000000 <= k <= 100000000

 1 #include<iostream>
 2 const int MAX_N = 100;
 3 int a[MAX_N];
 4 int n, k;
 5 using namespace std;
 6 bool dfs(int i, int sum)
 7 {
 8     if(i == n)
 9         return sum == k;
10     if(dfs(i + 1, sum))
11         return true;
12     if(dfs(i + 1, sum + a[i]))
13         return true;
14     return false;
15 }
16 
17 void solve()
18 {
19     if(dfs(0, 0))
20         cout << "Yes" << endl;
21     else
22         cout << "No" << endl;
23 }
24 
25 
26 int main()
27 {
28     cin >> n;
29     for(int i = 0; i < n; i++)
30         cin >> a[i];
31     cin >> k;
32     solve();
33     return 0;
34 }