Bitmasks in Competitive Programming: Trying Every Subset

When a problem has n ≤ 20 and asks you to choose some of the items, the intended solution is often to try every possible choice. There are 2ⁿ of them, about a million for n = 20, which is fast enough. Bitmasks are the cleanest way to list them all.

An integer as a set

Think of the bits of an integer as yes/no switches. With n items, bit i of a number says whether item i is in the set. For 4 items:

• 0000 (0) is the empty set.
• 0101 (5) is the set {item 0, item 2}.
• 1111 (15) is all four items.

Every integer from 0 to 2ⁿ − 1 is a different subset, and every subset appears exactly once. So a single for loop over those integers visits all subsets.

The bit operations you need

Goal	Expression
Is item i in the set?	mask & (1 << i)
Add item i	mask | (1 << i)
Remove item i	mask & ~(1 << i)
Number of items in the set	__builtin_popcount(mask)
Number of subsets of n items	1 << n

Example problem: dividing apples

There are n ≤ 20 apples with weights p₁, …, p_n. Split them into two groups so that the difference between the group weights is as small as possible. This is CSES 1623 – Apple Division.

Each mask chooses which apples go into group A. Group B gets the rest, so its weight is the total minus A. The difference is |total − 2A|. Try every mask and keep the smallest difference.

Code (C++)

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

int main() {
    int n;
    cin >> n;
    vector<long long> p(n);
    long long total = 0;
    for (auto &x : p) { cin >> x; total += x; }

    long long best = LLONG_MAX;
    // Each mask from 0 to 2^n - 1 describes one way to choose group A:
    // bit i set means apple i goes to group A.
    for (int mask = 0; mask < (1 << n); mask++) {
        long long a = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) a += p[i];
        best = min(best, llabs(total - 2 * a));   // |A - B| where B = total - A
    }
    cout << best << '\n';
    return 0;
}

Example

Weights 3 2 7 4 1, total 17. Putting {3, 4, 1} in one group (8) and {2, 7} in the other (9) gives a difference of 1. A difference of 0 is impossible because the total is odd, so 1 is optimal.

Complexity

2ⁿ masks, and O(n) work for each, gives O(2ⁿ · n). For n = 20 that is about 2 × 10⁷ operations. For n = 30 it would be 3 × 10¹⁰, which is why this technique is tied to small limits. My post on reading constraints has more on matching limits to techniques.

Common mistakes

• Writing 1 << n when n can be 31 or more. That overflows a 32-bit int; use 1LL << n.
• Operator precedence. mask & 1 << i == 0 does not mean what it looks like, because == binds tighter than &. Add parentheses: (mask & (1 << i)) == 0.
• Recomputing sums from scratch for each mask when n is near the limit. It works here, but for tighter problems you can build the sum of a mask from a smaller mask in O(1).

Where to go next

Bitmasks are also used as DP states. In “bitmask DP”, dp[mask] stores the best answer for a particular subset of items already used. That is how the travelling salesman problem is solved for n ≤ 20 in O(2ⁿ · n²).

Practice problems

• CSES 1623 – Apple Division: the problem in this post.
• Codeforces 1097B – Petr and a Combination Lock: for each rotation choose clockwise or counterclockwise, and check whether the total is a multiple of 360.