Bitmasking is one of the most powerful and elegant techniques in competitive programming. It allows us to represent subsets using bits and perform complete search efficiently.
Complete Search → Iterative Approach
We can iterate over all subsets of a set of size n using integers from 0 to (1 << n) - 1.
Each bit in the number represents whether we include the element or not.
Difference Between Terms
| Term | Meaning | Order Matters? |
|---|---|---|
| Subarray | Continuous part of an array | Yes |
| Subset | Any combination of elements | No |
| Subsequence | Elements in order, not necessarily contiguous | Yes |
Example
Suppose we have the array:
[1, 2, 5, 9]
Each bitmask from 0000 to 1111 (binary) represents a subset:
| Mask (binary) | Decimal | Subset Example |
|---|---|---|
| 0000 | 0 | {} |
| 0001 | 1 | {9} |
| 0010 | 2 | {5} |
| 0011 | 3 | {5, 9} |
| 0100 | 4 | {2} |
| 0101 | 5 | {2, 9} |
| 0110 | 6 | {2, 5} |
| 0111 | 7 | {2, 5, 9} |
| 1000 | 8 | {1} |
| 1111 | 15 | {1, 2, 5, 9} |
1 << n = (2^n) → total number of subsets.
Example 1: Count Subsequences with Sum = K
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int &x : a) cin >> x;
int res = 0;
for (int mask = 0; mask < (1 << n); ++mask) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) {
sum += a[i];
}
}
if (sum == k) ++res;
}
cout << res;
We loop through all 2^n masks and check which subsets have a sum equal to k.
Example 2: Apple Division (CSES Problem)
Find the minimum difference between the total weights of two groups of apples.
int n;
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;
int mn = INT_MAX;
for (int mask = 0; mask < (1 << n); ++mask) {
int g1 = 0, g2 = 0;
for (int i = 0; i < n; i++) {
if (mask >> i & 1) g1 += a[i];
else g2 += a[i];
}
mn = min(mn, abs(g1 - g2));
}
cout << mn;
Bitset
A bitset is an array of bits (0 or 1). It is more memory-efficient and provides useful built-in functions.
#include <bitset>
bitset<62> b;
Useful Methods
| Function | Description |
|---|---|
b.count() | Returns number of 1s |
b.to_string() | Converts to a string of 0s and 1s |
b.set() | Sets all bits to 1 |
b.reset() | Sets all bits to 0 |
b.all() | True if all bits = 1 |
b.any() | True if any bit = 1 |
b.none() | True if all bits = 0 |
b.to_ullong() | Converts to unsigned long long |
Example
bitset<8> a = 5; // 00000101
bitset<8> b = 9; // 00001001
bitset<8> c = a | b; // bitwise OR
cout << c << "\n"; // 00001101
cout << a[2] << "\n"; // access bit #2
a = ~a; // bitwise NOT
Complexity
- Operations on a 64-bit bitset → O(64)
- Operations on a 32-bit bitset → O(32)
Summary
- Use bitmasking to represent subsets efficiently.
- Iterate from
0to(1 << n) - 1for complete search. - Use
bitsetwhen you need fast operations on bits. - Common use cases: subset sum, partitioning, combinatorial search.








There is a slightly faster solution for both problems. Instead of recalculating the sum for each mask, you can update it based on the difference between the current and previous mask.
Using Gray code ordering ensures that only one element changes between consecutive masks. In contrast, normal binary ordering can flip multiple elements in a single step, so a single mask update may require several additions or subtractions, but summed over all $$$2^n$$$ masks, this results in $$$2^{n+1}−n−2$$$ total updates. With Gray code, the sum updates require exactly one addition or subtraction per mask, resulting in $$$\mathcal{O}(2^n)$$$ complexity instead of the usual $$$\mathcal{O}(2^n\cdot n)$$$. The idea is simple: track the previous mask, find the differing index, and update the sum accordingly.
This approach works for any “nice” ordering, but Gray code guarantees exactly one change per mask.
PS. I couldn't add code for the version without Gray code, so it's on Ideone.
That's Amazing