题目描述

小 X 和小 Y 分居两地了好长一段时间，小 Y 非常想念小 X。过几天小 Y 就能回来了，他想在当地的商店给小 X 购买一些纪念品，但是很不幸的是，小 Y 是一个穷鬼，他走到商店的橱窗前只觉得自己囊中羞涩，不能将展台上的东西各买一样。橱窗的展台上排列的 $n$个不同的纪念品，第$i$个纪念品的价格为 $p_{i}$，小 Y 手中的钱只有 $M$，他想问问你，他总共有多少种不同的方案来购买这些纪念品？

注意，小 Y 可以选择不把所有钱都花完。

输入格式

输入包含两行。第一行给出正整数 $n,m$。

第二行给出$n$个正整数 $p_{i}$，表示每个纪念品的价格。

输出格式

输出一行，表示方案的个数。 注意：答案$\le2^{40}$

样例输入

5 1000
100 1500 500 500 1000

样例输出

8

数据范围

$n\le40,m\le10^{18},$数据有一定梯度

我的TLE60分代码：

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,a[101],ans,nn,cnt;
void dfs(unsigned long long u,unsigned long long money)
{
  if(money>m)return;
  if(u==nn+1)
  {
    ans++;
    return;
  }
  dfs(u+1,money);
  dfs(u+1,money+a[u]);
}
int main()
{
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      cnt+=a[i];
    }
  nn=n;
  sort(a+1,a+n+1);
    while(cnt>m)
    {
      cnt-=a[nn];
      n--;
    }
   dfs(1,0);
  cout<<ans;
  return 0;
}

蹲大佬剪枝