二进制枚举子集

 1 int ans = 0;
 2 for (int i = 0; i < (1<<14); ++i) {
 3     int tot_1 = 0;
 4     int tot_0 = 0;
 5     int num = 2;
 6     for (int j = 0; j < 14; ++j) {
 7         if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1
 8             tot_1++;
 9             num = num * 2;
10         } else {
11             tot_0++;
12             num = num - 1;
13         }  
14     }
15     if (tot_1 == 5 && tot_0 == 9 && num == 1) {
16         ++ans; // 记录合法方案数
17     }
18 }

某君有 n个互不相同的正整数，现在他要从这 n 个正整数之中无重复地选取任意个数，并仅通过加法凑出整数 X。求某君有多少种不同的方案来凑出整数 X。

输入格式
第一行，输入两个整数 n,X(1≤n≤20,1≤X≤2000)。

接下来输入 n 个整数，每个整数不超过 100。

输出格式
输出一个整数，表示能凑出 X 的方案数。

样例输入
6 6

1 2 3 4 5 6

样例输出
4

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <stack>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 int a[25];
20 
21 int main()
22 {
23     int n,x;
24     scanf("%d %d",&n,&x);
25     for(int i=0;i<n;i++)
26         scanf("%d",&a[i]);
27     int ans=0;
28     for(int i=0;i<(1<<n);i++)
29     {
30         int sum=0;
31         for(int j=0;j<n;j++)
32         {
33             if(i&(1<<j)) sum+=a[j];
34         }
35         if(sum==x)    ans++;
36     }
37     printf("%d
",ans);
38     return 0;
39 }

样例输入

样例输出

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <stack>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 vector<int> vt[101];
20 int a[20];
21 
22 int main()
23 {
24     int n,m,k;
25     scanf("%d %d %d",&n,&m,&k);
26     for(int i=0;i<n;i++)
27     {
28         int x;
29         scanf("%d",&x);
30         for(int j=0;j<x;j++)
31         {
32             int t;
33             scanf("%d",&t);
34             vt[i].push_back(t);
35         }
36     }
37     int ans=0;
38     for(int i=0;i<(1<<k);i++)
39     {
40         set<int> st;
41         for(int j=0;j<k;j++)
42         {
43             if(i&(1<<j)) st.insert(j+1);
44         }
45         if(st.size()>m) continue;
46         int tot=0;
47         for(int j=0;j<n;j++)
48         {
49             vector<int>::iterator it;
50             for(it=vt[j].begin();it!=vt[j].end();it++)
51             {
52                 if(st.find(*it)==st.end()) break;
53             }
54             if(it==vt[j].end())
55                 tot++;
56         }
57         ans=max(ans,tot);
58     }
59     printf("%d
",ans);
60     return 0;
61 }