【题解】求和个数
题意
给你一个数列,求从中挑选出一些数进行求和,使和在
的区间内,请问有多少种方案呢。
题解
由于数组的长度只有
,所以我们可以枚举所有的组合,我们可以用二进制下
和
的关系来表示如何选择元素,其中
表示选择,
表示不选。例如
,表示选了
,
,别的不选。所有我们可以从
枚举到
。这样就可以包括所有的情况,然后对于每种情况我们求个和,判断其是否在
的范围内,若在就答案加一。
复杂度
时间复杂度
代码
#include<bits/stdc++.h> using namespace std; int a[25]; int main() { int n,l,r; scanf("%d%d%d",&n,&l,&r); for(int i=0;i<n;i++) scanf("%d",&a[i]); int ans=0; for(int i=0;i<(1<<n);i++) { long long sum=0; for(int j=0;j<n;j++) { if((i&(1<<j))!=0) sum+=a[j]; } if(sum>=l&&sum<=r) ans++; } printf("%d\n",ans); return 0; }