Bitmask Subset Enumeration

1. Algorithm & Complexity

Many problems over small sets (N ≤ ~20) can be solved by iterating all subsets. We represent each subset by an integer mask from 0…(1<<N)−1, where bit i of mask indicates whether element i is included.

1. Loop over all masks
   for (int mask = 0; mask < (1<<N); ++mask)
2. Examine bits of the mask
   Either by
   • iterating i=0…N−1 and checking if (mask & (1<<i)) …, or
   • using for (int s = mask; s; s &= s−1) to peel off lowest set bit.
3. Compute whatever you need (sum of selected elements, check property, combine DP states…).

Time Complexity

There are 2^N masks, and inspecting each takes O(N) or O(#bits) time.

• Worst‐case: O(N·2^N).
• If you only peel bits: O(2^N · popcount(avg)) = O(N·2^N) as well.

Memory Complexity

• O(1) extra if you just keep running counters.
• O(2^N) if you store DP values for every mask.

---

2. Easy Problems

2.1 – Codeforces “Subset Sum” (N ≤ 20)

Given an array A of N integers (N≤20) and a target S, determine if there is a subset whose sum equals S.

Input:
4 10
2 3 5 9

Output:
YES

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    bool found = false;
    int total = 1 << N;
    for (int mask = 0; mask < total; ++mask) {
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            if (mask & (1 << i)) sum += A[i];
        }
        if (sum == S) { found = true; break; }
    }

    cout << (found ? "YES\n" : "NO\n");
    return 0;
}

2.2 – Codeforces “Count Distinct Subset Sums”

Given N (≤20) non‐negative integers, find the number of distinct sums over all subsets.

Input:
3
1 2 2

Output:
3

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int N; 
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    set<int> sums;
    for (int mask = 0; mask < (1 << N); ++mask) {
        int sum = 0;
        for (int i = 0; i < N; ++i)
            if (mask & (1 << i)) sum += A[i];
        sums.insert(sum);
    }

    cout << sums.size() << "\n";
    return 0;
}

---

3. Intermediate Problems

3.1 – Codeforces “Meet-in-the-Middle Subset Sum”

When N≈40, split into two halves of size N/2, enumerate subsets in each half (2²⁰ each) and use two‐pointer or hashing to answer sum‐queries in O(2^N/2·(N/2)).

Input:
6 10
3 34 4 12 5 2

Output:
YES

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N, S;
    cin >> N >> S;
    vector<int> A(N);
    for(int i=0;i<N;i++) cin >> A[i];

    int n1 = N/2, n2 = N - n1;
    vector<int> sums1, sums2;
    // half 1
    for(int mask=0; mask < (1<<n1); ++mask){
        int sum=0;
        for(int i=0;i<n1;i++) if(mask &(1<<i)) sum+=A[i];
        sums1.push_back(sum);
    }
    // half 2
    for(int mask=0; mask < (1<<n2); ++mask){
        int sum=0;
        for(int i=0;i<n2;i++) if(mask &(1<<i)) sum+=A[n1+i];
        sums2.push_back(sum);
    }
    sort(sums2.begin(), sums2.end());
    // for each in sums1, look for S−sum in sums2
    for(int x : sums1){
        if (binary_search(sums2.begin(), sums2.end(), S - x)) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}

3.2 – Codeforces “SOS DP: Sum Over Subsets”

Given an array F of size 2^N, compute for each mask the sum of F over all submasks of that mask in O(N·2^N).

Input:
3
1 2 3 4 5 6 7 8

Output:
1 3 4 10 5 11 12 36

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N; 
    cin >> N;
    int M = 1 << N;
    vector<long long> F(M);
    for(int i=0;i<M;i++) cin >> F[i];

    // SOS DP: for each bit
    for(int b=0; b<N; ++b){
        for(int mask=0; mask<M; ++mask){
            if (mask & (1<<b))
                F[mask] += F[mask ^ (1<<b)];
        }
    }

    for(int i=0;i<M;i++){
        cout << F[i] << (i+1<M?' ':'\n');
    }
    return 0;
}

---

4. Hard Problem

4.1 – Codeforces “Traveling Salesman with Bitmask DP”

Given a complete graph on N≤20 nodes with weights W[u][v], find the minimum Hamiltonian cycle cost. Use DP[mask][u] = min cost to visit subset mask and end at u:

Input:
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Output:
80

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18;

int main(){
    int N; 
    cin >> N;
    vector<vector<long long>> W(N, vector<long long>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin >> W[i][j];

    int M = 1<<N;
    // dp[mask][u]
    vector<vector<long long>> dp(M, vector<long long>(N, INF));
    dp[1][0] = 0;  // start at 0

    for(int mask=1; mask<M; ++mask){
        for(int u=0; u<N; ++u){
            if (!(mask & (1<<u))) continue;
            long long cur = dp[mask][u];
            if (cur == INF) continue;
            // try to go to v not in mask
            for(int v=0; v<N; ++v){
                if (mask & (1<<v)) continue;
                int nxt = mask | (1<<v);
                dp[nxt][v] = min(dp[nxt][v], cur + W[u][v]);
            }
        }
    }

    long long ans = INF;
    // return to 0
    for(int u=1; u<N; ++u)
        ans = min(ans, dp[M-1][u] + W[u][0]);

    cout << ans << "\n";
    return 0;
}