- int ans = 0;
- for (int i = 0; i <(1<<14); ++i) {
- int tot_1 = 0;
- int tot_0 = 0;
- int num = 2;
- for (int j = 0; j < 14; ++j) {
- if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1
- tot_1++;
- num = num * 2;
- } else {
- tot_0++;
- num = num - 1;
- }
- }
- if (tot_1 == 5 && tot_0 == 9 && num == 1) {
- ++ans; // 记录合法方案数
- }
- }
某君有 n 个互不相同的正整数, 现在他要从这 n 个正整数之中无重复地选取任意个数, 并仅通过加法凑出整数 X. 求某君有多少种不同的方案来凑出整数 X.
输入格式
第一行, 输入两个整数 n,X(1≤n≤20,1≤X≤2000).
接下来输入 n 个整数, 每个整数不超过 100.
输出格式
输出一个整数, 表示能凑出 X 的方案数.
样例输入
6 6
1 2 3 4 5 6
样例输出
- 4
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include <string>
- #include <math.h>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <set>
- #include <stack>
- #include <map>
- #include <sstream>
- const int INF=0x3f3f3f3f;
- typedef long long LL;
- const int mod=1e9+7;
- const int maxn=1e5+10;
- using namespace std;
- int a[25];
- int main()
- {
- int n,x;
- scanf("%d %d",&n,&x);
- for(int i=0;i<n;i++)
- scanf("%d",&a[i]);
- int ans=0;
- for(int i=0;i<(1<<n);i++)
- {
- int sum=0;
- for(int j=0;j<n;j++)
- {
- if(i&(1<<j)) sum+=a[j];
- }
- if(sum==x) ans++;
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3350528.html