Subset Generation (DFS vs Bitmask Thinking)

Subset generation connects recursion (include/exclude loop) with bitmasks for n≤20: iterate mask from 0 to (1<<n)-1 and interpret bits.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Map index i ↔ bit i. For Gray code order or minimal change, advanced enumeration—optional.

Try this in Python

def subsets_bit(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    out: list[list[int]] = []
    for mask in range(1 << n):
        cur = [nums[i] for i in range(n) if mask >> i & 1]
        out.append(cur)
    return out


print(subsets_bit([1, 2]))

Common mistakes

• 1 << n overflow in languages with fixed width—Python OK.
• Off-by-one in bit length (n bits vs 1<<n values).

Key takeaways

• For interview clarity, start DFS; mention bitmask as optimization.
• if mask >> i & 1 test membership.