백준 1208번 부분수열의 합2(C++)⭐⭐⭐

https://www.acmicpc.net/problem/1208

 

부분수열이란게 뭘 연속된걸 말하는지 뭔지 헷갈려허 해맸다

그니까 최대 40개중 2^40 으로 그냥 고르면 되는거였다

다만 2^40 = 1억이 넘어가서 

2^20으로 따로따로 부분수열 구해서 합의 결과를 저장한다. 

부분 수열 구하는건 비트마스킹으로 조합을 구한다. 

그리고 한가지 두개로 쪼갠거에 비트마스킹해서 둘다 아무것도 안골랐을때가 합이 0인경우에 포함되서 

0일 경우에만 1을 빼주면된다

#include <iostream>
#include <vector>
#include <algorithm>
#include<queue>
#include<map>
#include<unordered_map>
#include<string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
  
    int n, s;
    cin >> n >> s;
    vector<long long>arr1;
    vector<long long>arr2;
    
    long long cnt = 0;
    //겹치면 안됨 
    //2^40 -> 2^20
    int t;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (i < n / 2)arr1.push_back(t);
        else arr2.push_back(t);
    }
    
    vector<long long>sum1;
    vector<long long>sum2;
    long long l1 = arr1.size();
    long long l2 = arr2.size();
    //조합
    for (int i = 0; i < (1ll <<l1); i++){
        long long sum = 0;
        for (int j = 0; j < arr1.size(); j++) {
            if (i & (1 << j))sum += arr1[j];
        }
        sum1.push_back(sum);
    }
    for (int i = 0; i < (1ll << l2); i++) {
        long long sum = 0;
        for (int j = 0; j < arr2.size(); j++) {
            if (i & (1<<j))sum += arr2[j];
        }
        sum2.push_back(sum);
    }

    //두배열 
    sort(sum1.begin(), sum1.end());
    sort(sum2.begin(), sum2.end());
    //더해서 0인건지 아예포함 안해서 0인건지 
   
    long long ap = 0;
    long long bp = sum2.size() - 1;
    while (ap < sum1.size() && bp >= 0) {

        long long num1 = sum1[ap];
        long long num2 = sum2[bp];
        //cout << ap << " " << bp << "탐색중\n";
        if ((num1 + num2) == s) {
            long long anum = 0;
            long long bnum = 0;

            while (ap <sum1.size() && sum1[ap] == num1) {
                anum++; ap++;
              //  cout << "추가1";
            }
            while (bp>=0 && sum2[bp] == num2) {
                bnum++; bp--;
               // cout << "추가2";
            }
          //  cout << ap << " " << bp << "까지 탐색\n";
            cnt += (anum * bnum);
        }
        else if ((num1 + num2)< s) {
            ap++;
        }
        else {
            bp--;
        }

    }

    if (s == 0)cout << cnt - 1;
    else cout << cnt;
    //if ((uit - lit) > 0)cout << uit - lit;
    //else cout << 0;
}