某君有 n个互不相同的正整数,现在他要从这 n 个正整数之中无重复地选取任意个数,并仅通过加法凑出整数 X。求某君有多少种不同的方案来凑出整数 X。
输入格式
第一行,输入两个整数 n,X(1≤n≤20,1≤X≤2000),X(1≤n≤20,1≤X≤2000)。
接下来输入 n 个整数,每个整数不超过 100。
输出格式
输出一个整数,表示能凑出 X 的方案数。
样例输入
6 6
1 2 3 4 5 6
样例输出
4
关于二进制枚举的最通俗易懂的讲解:https://www.cnblogs.com/SunQi-lvbu/p/7305779.html
AC代码:
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
int n,m,c,cum=;
int a[];
cin>>n>>m;
int i,j;
for(i=;i<n;i++){
cin>>a[i];
}
int ans=;
for(i=;i<(<<n);i++){//表示0~2^n-1个状态
int num=;
for(j=;j<n;j++){//遍历二进制的每一位
if(i&(<<j)){//判断二进制第j位是否存在
num+=a[j];
}
}
if(num==m){
ans++;
}
}
cout<<ans;
return ;
}