BitsAlgorithmaka enumerate subsets, submask enumeration, iterate masks

Subset Generation with Bitmasks

Enumerate every subset of n items by counting masks from 0 to 2^n - 1, and every submask of a mask with s = (s - 1) & mask.

▶ VisualizePattern: BacktrackingPractice (3)
Progress

Overview

A subset of n items is a bit mask (see Bit Masks), so the integers 0 .. 2^n - 1 are all subsets. One for loop enumerates them; testing bit i of the counter tells whether item i is included. This replaces the recursive Subsets (Power Set) backtracking with a flat loop and is the standard way to brute-force n ≤ 20.

The second loop enumerates the submasks of a given mask m in decreasing order: start with s = m, then repeatedly s = (s - 1) & m until s wraps to 0 (handle the empty submask explicitly). Over all m from 0 to 2^n - 1 the total number of (m, s) pairs is 3^n, because each element is either in neither, in m only, or in both.

Submask enumeration is the engine of subset-sum-over-subsets DP (SOS), set-partition DP (dp[m] = min over s ⊆ m of dp[m ^ s] + cost(s)), and problems like "split the items into two groups".

subsetsbitmasksubmaskenumerationO(2^n)O(3^n)

Intuition

A mental model before the formal terms.

Counting from 0 to 2^n - 1 in binary is walking through every pattern of n on/off switches exactly once — an odometer for subsets. No recursion, no visited set: the counter itself is the state.

For submasks, imagine only some switches are unlocked (the bits of m). Subtracting 1 and re-masking is "decrement, but skipping the locked switches": the locked ones snap back to off, and the unlocked ones count down through every combination.

How it works

  1. All subsets: for mask in 0 .. (1 << n) - 1: for each i in 0 .. n - 1, if (mask >> i) & 1 then item i is in this subset. Build the subset or accumulate its value.
  2. Incremental sums avoid the inner loop: sum[mask] = sum[mask & (mask - 1)] + a[ctz(mask)] computes every subset sum in O(2^n) total.
  3. Submasks of m: s = m; while true: process(s); if s == 0: break; s = (s - 1) & m. This visits every s with s & m == s exactly once, from m down to 0.
  4. Gray-code order (mask ^ (mask >> 1)) visits subsets so that consecutive ones differ by one element — useful when each subset is built by one add/remove from the previous.
  5. Subsets of exactly k elements: iterate all masks and filter by popcount, or use Gosper's hack to jump between k-bit masks directly.

Why it works

The map from subsets to integers 0..2^n - 1 (item i ↔ bit i) is a bijection, so the counter loop visits each subset exactly once with no duplicates and no misses.

Submask step: s - 1 flips the lowest set bit of s and all bits below it; ANDing with m restores zeros outside m. The result is the largest integer less than s whose set bits lie inside m, so the sequence strictly decreases through every submask and cannot skip any.

3^n total pairs: for each of the n positions, the pair (m, s) has three consistent states (bit in neither, in m only, in both), and each combination of states is one distinct pair.

Recognition

How to tell a problem wants this.

  • n ≤ 20 (or ≤ 15 with a per-subset inner loop) and the statement asks for "all subsets", "any combination", "choose a group of items".
  • A DP over sets where a transition removes a *subset* of the current set at once (partition into groups, assign teams).
  • Sum over subsets / superset sums (SOS DP) on an array indexed by mask.
“all combinations” → Backtracking“number of ways” → Dynamic Programming“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

mask
0
7
0
6
0
5
0
4
0
3
0
2
0
1
0
0
= 0
items (bit i ↔ items[i])
bit 0: 1bit 1: 2bit 2: 3
1/343 items give 2^3 = 8 subsets. Each mask from 0 to 7 encodes one subset: bit i says whether items[i] is included.
Bit i = 1: items[i] is in the subsetBit i = 0: items[i] is left outBit being tested
PseudocodeLearn Subset Generation with Bitmasks →
1for mask in 0 .. 2^n - 1:
2  subset = []
3  for i in 0 .. n-1:
4    if mask & (1 << i): subset.append(items[i])
5  output subset
Variables
n3
total8
Complexity
best O(2^n)
avg O(2^n · n)
worst O(3^n)
space O(2^n)
Speed

Pseudocode

1// all subsets
2for mask in 0 .. 2^n - 1:
3  subset = [a[i] for i in 0..n-1 if (mask >> i) & 1]
4// submasks of m, descending
5s = m
6loop:
7  process(s)
8  if s == 0: break
9  s = (s - 1) & m

Implementations

1from typing import List
2 
3 
41 · Enumerate all subsets
5def all_subsets(items: List[int]) -> List[List[int]]:
6    n = len(items)
7    out = []
8    for mask in range(1 << n):
92 · Decode the mask into elements
10        subset = [items[i] for i in range(n) if mask & (1 << i)]
11        out.append(subset)
12    return out
13 
14 
153 · Enumerate submasks of a mask
16def submasks(mask: int) -> List[int]:
17    out = []
18    s = mask
19    while True:
20        out.append(s)
21        if s == 0:
22            break  # break AFTER emitting 0: (0 - 1) & mask == mask would loop forever
23        s = (s - 1) & mask
24    return out
25 
26 
274 · Demo
28if __name__ == "__main__":
29    assert len(all_subsets([1, 2, 3])) == 8
30    assert len(submasks(0b1011)) == 8  # 2^popcount(mask) submasks
Walkthrough
  1. range(1 << n) yields every mask; Python ints are unbounded so nothing special happens at 31 or 63 bits — only time and memory limit n.
  2. The decode is a list comprehension filtered by mask & (1 << i) — the direct Python idiom for "bit i set".
  3. The submask loop mirrors the classic trick; Python's & on negative ints uses infinite two's complement, so skipping the 0-break would also cycle here ((-1) & mask == mask).
  4. The while True with a post-append break keeps 0 in the output.
Complexity (this implementation)
time O(2^n * n) all subsets, O(2^k) submasks · space O(2^n * n)

Interpreter overhead makes n above ~20 painful even though the ints themselves are unbounded.

Language notes
  • itertools.combinations/chain can generate subsets too, but masks are the right tool when subsets index into a DP table.
  • Python has no 32-bit ceiling: 1 << 100 just works — masks over 64 items are possible, unlike C++/JS.
  • mask.bit_count() (3.10+) gives subset size; format(mask, "b") prints it.
Common mistakes in this language
  • Using while s > 0 and losing the empty submask.
  • Building subsets with repeated list.insert(0, x) — O(n) each; append in index order instead.
  • Forgetting that generating all subsets of 30+ items is 10^9+ lists regardless of language.
Language differences that matter here
  • Mask width: C++ picks it via the type (1ULL << i for 64 items); JS/TS number masks stop at 30–31 bits (then BigInt/bigint); Python ints are unbounded so any subset universe fits.
  • 1 << 31: UB on C++ int (use unsigned), -2147483648 in JS/TS, and simply 2147483648 in Python.
  • The (s - 1) & mask submask trick is identical everywhere, including the infinite-loop hazard at 0 — -1 & mask == mask holds in 32-bit two's complement (JS/TS), width-N unsigned wraparound (C++), and Python's infinite two's complement.
  • Subset size: C++20 std::popcount, Python int.bit_count(), JS/TS need a hand-rolled popcount.

Complexity

Best
O(2^n)
Average
O(2^n · n)
Worst
O(3^n)
Space
O(2^n)

All subsets: O(2^n) masks, times O(n) if each is materialized. Submasks of one mask m: O(2^popcount(m)). Submasks of every mask: O(3^n) total.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • n ≤ 20–22 brute force over all subsets, especially when the check per subset is O(1) via incremental sums.
  • Set-partition and assignment DP whose transitions remove a whole subset at once.
  • Meet-in-the-middle: enumerate subsets of each half (2^(n/2) each) and combine.
Avoid it when
  • n > ~25: 2^25 masks is 33 million, 3^20 is already 3.5 billion — look for pruning, greedy, or a polynomial structure.
  • When subsets must be produced in lexicographic order or with constraints that prune most branches — recursive Subsets (Power Set) backtracking prunes; a mask loop cannot.
  • In JavaScript when n ≥ 31 — 1 << 31 is negative.

Alternatives

Subsets (Power Set)Combinations (n choose k)Bitmask DP

Common mistakes

  • Infinite loop on submasks: writing while (s > 0) { s = (s - 1) & m; } skips the empty submask, while while (s != 0) after processing 0 wraps to -1 & m = m and never ends. Process first, then test s == 0, then step.
  • Double counting in partition DP when the removed subset is not forced to contain a fixed element (e.g. the lowest set bit).
  • Allocating 2^n arrays of size n — build subsets lazily or store sums, not lists.
  • Using mask & (1 << i) == 1 for membership; the result is 1 << i, so compare with != 0.

Interview patterns

  • Subsets / Subsets II (with duplicates: sort, and skip masks that select a later duplicate without the earlier one).
  • Partition to k equal-sum subsets: dp[mask] reachable if some element extends a valid prefix.
  • Shortest path visiting all nodes: BFS over (node, mask); the answer is the first state with mask == full.
  • Sum over subsets (SOS DP): for i in 0..n-1: for mask: if mask has bit i: f[mask] += f[mask ^ (1 << i)] in O(n · 2^n).
Interview questions on this
Mock interviews

Example problems

Shortest Path Visiting All NodeshardSubsetsmediumPartition Equal Subset Summedium