【CSES】1628. Meet in the Middle

題目連結

時間複雜度

$O (2^{\frac{N}{2}} + l o g N)$

解題想法

這一題最樸素的作法是枚舉所有子集合，然後加總就可以得到答案了

但是這樣的做法時間複雜度是

O (2^{N})

又因為 N < 41 所以想必這個速度絕對不會過

因此我們要做的是將先將陣列中的數字分成前半跟後半兩堆，分別枚舉兩堆數字中的所有子集合的和，並透過二分搜找出合為目標的答案數量

完整程式

















































/* Question : CSES 1628. Meet In The Middle */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 40 + 50;
const int Mod = 1e9 + 7;
int n, x, res, arr[MAXN];
vector<int> l, r;

void sum( int st, int ed, vector<int>& v ){
    int len = ed - st + 1;
    for( int i = 0 ; i < ( 1 << len ) ; i++ ){
        int val = 0;
        for( int j = 0 ; j < len ; j++ ){
            if( i & ( 1 << j ) ) val += arr[st+j];
        }
        v.pb(val);
    }

    sort(v.begin(), v.end());
}

signed main(){
    opt;
    cin >> n >> x;
    for( int i = 1 ; i <= n ; i++ ) cin >> arr[i];

    sum(1, n/2, l);
    sum(n/2+1, n, r);

    for( auto i : l ){
        int dif = x - i;
        res += upper_bound(r.begin(), r.end(), dif) - lower_bound(r.begin(), r.end(), dif);
    }

    cout << res << "\n";
}