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

dfs + 简单剪枝

1 #include 
     
       2 #include 
      
        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 }