题目描述
某君有n个互不相同的正整数,现在他要从这n个正整数之中无重复地选取任意个数,并仅通过加法凑出整数X。求某君有多少种不同的方案来凑出整数X。
输入
第一行,输入两个整数n,X(1≤n≤20,1≤X≤2000)。
接下来输入n个整数,每个整数不超过100。
输出
输出一个整数,表示能凑出X的方案数。
样例输入 Copy
6 6
1 2 3 4 5 6
样例输出 Copy
4
解题思路:求这个集合的全部子集(可以仿照书上的例题),判断子集中的总和是否为X,是的话,方案数加一。
#include<bits/stdc++.h> using namespace std; int main(){ int n,X; cin>>n>>X; int arr[25]; for(int i=0;i<n;i++){ cin>>arr[i]; } int ans=0; for(int i=0;i<(1<<n);i++){ //1左移两位变成2^n,从0~2^n-1, 二进制上的0表示该位不取,1表示取 int sum=0; for(int j=0;j<n;j++){ if(i&(1<<j)){ //判断第j位是否为大于0 sum+=arr[j]; } } if(sum==X) ans++; } printf("%d\n",ans); return 0; }
书中例题,打印n个数的子集,全排列。
#include<bits/stdc++.h> using namespace std; void printf_subset(int n){ for(int i=0;i<(1<<n);i++){ //从0~2^n-1, 二进制上的0表示该位不取,1表示取 for(int j=0;j<n;j++){ if(i & (1<<j)){ //从i的最低位开始逐个检查每一位,如果是1,打印 cout << j<< " "; } } cout << endl; } } int main() { int n; cin >>n; printf_subset(n); return 0; }
核心代码的图片分析