【题解】求和个数

题意

给你一个数列,求从中挑选出一些数进行求和,使和在的区间内,请问有多少种方案呢。

题解

由于数组的长度只有,所以我们可以枚举所有的组合,我们可以用二进制下的关系来表示如何选择元素,其中表示选择,表示不选。例如,表示选了,别的不选。所有我们可以从枚举到。这样就可以包括所有的情况,然后对于每种情况我们求个和,判断其是否在的范围内,若在就答案加一。

复杂度

时间复杂度

代码

#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;
}

全部评论

相关推荐

星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务