部分和问题

问题描述 n个数取其中部分之和能否构成k

dfs + 简单剪枝

 1 #include <iostream>
 2 #include <fstream>
 3 
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 
 8 //每一个数要么选要么不选 所以复杂度是O(2^n)
 9 //还能剪枝  因为当sum超过k时 状态无论如何转移都无法成功
10 ll a[128];
11 ll k;
12 int n;
13 bool dfs(int t, ll s)
14 {
15     if (s == k)
16     {
17         return true;
18     }
19     //剪枝
20     if (s > k) return false;
21     if (t == n) return false;
22     return ( dfs(t+1, s+a[t]) || dfs(t+1, s) );
23 }
24 int main()
25 {
26     ifstream cin ("in.txt");
27     cin >> n;
28     for (int i = 0; i < n; i++)
29     {
30         cin >> a[i];
31     }
32     cin >> k;
33     if ( dfs(0, 0) )cout << "yes" << endl;
34     else cout << "no" << endl;
35 }