BitsBit Manipulation
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.
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 subsetVariables
n3
total8
Complexity
best O(2^n)
avg O(2^n · n)
worst O(3^n)
space O(2^n)
Speed