小 X 和小 Y 分居两地了好长一段时间，小 Y 非常想念小 X。过几天小 Y 就能回来了，他想在当地的商店给小 X 购买一些纪念品，但是很不幸的是，小 Y 是一个穷鬼，他走到商店的橱窗前只觉得自己囊中羞涩，不能将展台上的东西各买一样。橱窗的展台上排列的 n 个不同的纪念品，第 i 个纪念品的价格为 p i

，小 Y 手中的钱只有 M，他想问问你，他总共有多少种不同的方案来购买这些纪念品？

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

输入格式 输入包含两行。第一行给出正整数

n,m。第二行给出

n 个正整数 p i ​ ，表示每个纪念品的价格。

输出格式 输出一行，表示方案的个数。注意：答案 ≤ 2^40

#include <iostream>  
#include <vector>  
  
using namespace std;  
  
typedef unsigned long long ull;  
  
// 全局变量来存储结果和当前的总和  
ull result = 0;  
int currentSum = 0;  
  
// DFS 函数  
void dfs(const vector<int>& prices, int index, int m) {  
    // 如果当前索引超出了价格数组的长度，说明已经遍历完所有商品  
    if (index == prices.size()) {  
        // 如果当前总和不超过 m，则这是一种有效的购买方案  
        if (currentSum <= m) {  
            result++;  
        }  
        return;  
    }  
      
    // 不选择当前商品，继续搜索  
    dfs(prices, index + 1, m);  
      
    // 选择当前商品，并更新当前总和，然后继续搜索  
    if (currentSum + prices[index] <= m) {  
        currentSum += prices[index];  
        dfs(prices, index + 1, m);  
        currentSum -= prices[index]; // 回溯，撤销选择  
    }  
}  
  
int main() {  
  ios::sync_with_stdio(0);
  cin.tie(0);
    int n, m;  
    cin >> n >> m;  
      
    vector<int> prices(n);  
    for (int i = 0; i < n; ++i) {  
        cin >> prices[i];  
    }  
      
    // 调用 DFS 函数从第 0 个商品开始搜索  
    dfs(prices, 0, m);  
      
    // 输出结果  
    cout << result << endl;  
      
    return 0;  
}
//逆天马蜂见谅