STL

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, nn, m;
int a[25];
vector<int> x, y;
// 当前考虑第 now 个数选不选
// 之前的所有数之和为 sum
// 所有产生的数丢进 all
void dfs(int now, int sum, vector<int> &all)
{
    if (now > nn)
        return;
    // 选
    all.push_back(sum + a[now]);
    dfs(now + 1, sum + a[now], all);
    // 不选
    dfs(now + 1, sum, all);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    nn = n / 2;
    for (int i = 1; i <= nn; i++)
        cin >> a[i];
    x.push_back(0);
    dfs(1, 0, x);
    nn = n - nn;
    for (int i = 1; i <= nn; i++)
        cin >> a[i];
    y.push_back(0);
    dfs(1, 0, y);
    // 算组合的方案
    int ans = 0; // 一场都不看的特判
    sort(y.begin(), y.end());
    for (int i = 0; i < x.size(); i++)
    {
        // y[pos] 是第一个大于 m-x[i] 的数
        // 前面刚好有 y[0]~y[pos-1] 共 pos 个小于等于 m-x[i] 的数
        int pos = upper_bound(y.begin(), y.end(), m - x[i]) - y.begin();
        ans += pos;
    }
    cout << ans;
    return 0;
}

朴素写法

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, nn, m;
int a[25];
int xTot, x[(1 << 20) + 5]; // x[1]~x[xTot]
int yTot, y[(1 << 20) + 5]; // y[1]~y[yTot]
void dfsX(int now, int sum)
{
    if (now > nn)
        return;
    // 选
    xTot++;
    x[xTot] = sum + a[now];
    dfsX(now + 1, sum + a[now]);
    // 不选
    dfsX(now + 1, sum);
}
void dfsY(int now, int sum)
{
    if (now > nn)
        return;
    // 选
    y[++yTot] = sum + a[now];
    dfsY(now + 1, sum + a[now]);
    // 不选
    dfsY(now + 1, sum);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    nn = n / 2;
    for (int i = 1; i <= nn; i++)
        cin >> a[i];
    xTot = 1;
    x[xTot] = 0;
    dfsX(1, 0);
    nn = n - nn;
    for (int i = 1; i <= nn; i++)
        cin >> a[i];
    y[yTot = 1] = 0;
    dfsY(1, 0);
    // 算组合的方案
    int ans = 0; // 一场都不看的特判
    sort(y + 1, y + yTot + 1);
    for (int i = 1; i <= xTot; i++)
    {
        // y[pos] 是第一个大于 m-x[i] 的数
        // 前面刚好有 y[1]~y[pos-1] 共 pos-1 个小于等于 m-x[i] 的数
        int pos = upper_bound(y + 1, y + yTot + 1, m - x[i]) - y;
        ans += pos - 1;
    }
    cout << ans;
    return 0;
}