Ta biết được rằng khi chọn các số trong dãy ~a~ cùng lúc thì ta chỉ được chọn nhiều nhất ~3~ số. Bên cạnh đó, với giới hạn lớn nhất là ~n = 300~, ta có thể duyệt chọn cùng lúc ~3~ số bằng ~3~ vòng lặp lồng nhau.

Sau khi lần lượt thu được các giá trị từ việc chọn ~1~ số, chọn ~2~ số cùng lúc và chọn ~3~ số cùng lúc, ta sẽ lọc đi các giá trị trùng nhau và số lượng các giá trị còn lại sẽ là đáp án.

Độ phức tạp: ~O(n^3)~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 300;

int a[N+9];
int n,W;

int main()
{
    if (fopen(name".INP","r"))
        freopen(name".INP","r",stdin),
        freopen(name".OUT","w",stdout);

    fastIO

    cin>>n>>W;


    vector<int> v;
    for (int i = 1;i <= n; ++i)
    {
        cin>>a[i];
        if (a[i] <= W) v.push_back(a[i]);
    }

    if (n >= 2)
    {
        for (int i = 1;i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                if (a[i] + a[j] <= W) v.push_back(a[i] + a[j]);
    }

    if (n >= 3)
    {
        for (int i = 1;i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                for (int k = j + 1; k <= n; ++k)
                    if (a[i] + a[j] + a[k] <= W) v.push_back(a[i] + a[j] + a[k]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    cout<<(int)v.size();
}