Subsets and Power Set
Generate all subsets of a set using backtracking and bit-masking, handling duplicates by sorting and skipping repeated elements.
Subsets and the Power Set
The power set of a set S is the collection of all possible subsets of S, including the empty set and S itself. A set of n elements has exactly 2ⁿ subsets. For [1, 2, 3], the 8 subsets are: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. This is a fundamental combinatorial problem that appears in interview questions about finding all possible combinations, partitions, or choices.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Backtracking Subset Generation
Use the choose-explore-unchoose template. The key design decision: at each recursive call, add the current partial path to results immediately (before choosing more elements). This way, every state — empty, partial, and full — is captured as a valid subset. Advance the start index to only consider elements to the right of the last chosen element, ensuring no duplicates and preserving order.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]