patternDSA/Subsets

Core Pattern → Pattern 20

Subsets

BFS expansion or DFS backtracking. Every subset and permutation problem is a variation. append → recurse → pop is the universal backtrack pattern.

Frequency:★★★★☆

·~30 min·Intermediate–Hard·9 problems

Prev Backtracking

The Core Shock

Building subsets naively = combinatorial explosion. BFS one-liner doubles the list on each element: result += [s+[num] for s in result]

Nested loop for-each-element

Wrong/missing subsets

Can't enumerate all combinations with simple loops — miss most subsets

BFS: double the list each step

O(n·2ⁿ) — complete

One line per element. Every existing subset gets a new version with num appended.

The BFS insight: each new element either is or isn't in a subset. For every existing subset, we create one copy with the element appended. Starting from [[]], adding element 1 gives [[], [1]]. Adding 2 gives [[], [1], [2], [1,2]]. Adding 3 gives all 8 subsets. For permutations and constrained generation (parentheses, BSTs), DFS backtracking is cleaner.

BFS Expansion vs DFS Backtracking

Know which approach fits the problem before writing any code.

BFS Iterative Expansion

Use when: Subsets, combinations, power set. Order doesn't matter. No constraints on path.

How: Start with [[]]. For each element, extend every existing subset. result += [s+[x] for s in result]

SubsetsSubsets with DuplicatesCombinationsPower Set

DFS Backtracking

Use when: Permutations, constrained generation (parens, abbreviations). Order matters or constraints mid-path.

How: append → recurse → pop. Base case returns or records result. Prune with constraint checks.

PermutationsLetter Case PermutationsBalanced ParenthesesAbbreviationsUnique BSTs

The 3-Step Framework

One pattern covers both BFS and DFS variants.

BFS: result += [s + [num] for s in result]

For subsets: start result=[[]], loop over each num. In one line, double the result list by appending num to every existing subset. For duplicates: sort first, only extend subsets added in the LAST round (tracked via a start index).

result = [[]]
for num in nums:
    result += [s + [num] for s in result]

# Duplicates:
for i, num in enumerate(nums):
    if i > 0 and nums[i] == nums[i-1]:
        new = [s + [num] for s in result[start:]]
    else:
        start = len(result)
        new = [s + [num] for s in result]
    result += new

The list comprehension result += [s+[num] for s in result] is the entire BFS expansion in one line. For duplicates, the start index separates 'newly added last round' from 'all previously added'.

DFS: append → recurse(next_start) → pop

For DFS backtracking: add current element to path, recurse with updated state, then remove (backtrack). The recursion naturally explores all branches. Record result at the right depth (every node for subsets, leaf only for permutations).

def backtrack(start, path):
    result.append(list(path))  # subsets: record every node
    for i in range(start, n):
        path.append(nums[i])
        backtrack(i + 1, path)   # next must come after i
        path.pop()               # backtrack

# Permutations: record only at leaf
def bt(path, remaining):
    if not remaining:
        result.append(list(path))
        return
    for i, x in enumerate(remaining):
        path.append(x)
        bt(path, remaining[:i]+remaining[i+1:])
        path.pop()

The difference: subsets record at EVERY recursive call (including before the loop). Permutations record only when remaining is empty (leaf). Combinations record when path length equals k.

Prune: add constraints before recursing

Balanced parentheses: open < n (can open), close < open (can close). This prunes the tree from exponential to Catalan(n) valid outputs. Abbreviations, case variations: branch based on character type. Evaluate expression: split on operators and recurse left/right.

# Balanced parentheses pruning
def bt(s, open, close):
    if len(s) == 2*n: result.append(s); return
    if open < n:
        bt(s+'(', open+1, close)
    if close < open:           # can only close unclosed
        bt(s+')', open, close+1)

# Case permutations pruning
if ch.isdigit():
    bt(idx+1, path+[ch])       # one branch
else:
    bt(idx+1, path+[ch.lower()])
    bt(idx+1, path+[ch.upper()])

Pruning is what makes constrained generation practical. Without the 'close < open' check, balanced parentheses generates all 2^(2n) strings then filters. With it, only Catalan(n) valid strings are ever generated.

Pattern Recognition

'All possible', 'generate', 'enumerate' → Subsets pattern.

Use Subsets Pattern When

"Find all subsets", "power set", "all combinations"

"All permutations" of a set or string

"Generate all valid ___" (parentheses, expressions)

Find all unique abbreviations of a word

"All structurally unique BSTs" for n nodes

Split expression on operators, evaluate all ways

Any problem needing all combinations/arrangements

Constraint satisfaction with exhaustive search

Common Pitfalls

Subsets with duplicates: forgetting to sort input first

Duplicates: extending ALL subsets instead of only last round's

Backtracking: result.append(path) — appends reference, not copy

Backtracking: forgetting path.pop() → stale elements contaminate next branch

Balanced parens: allowing close >= open → unbalanced strings

Permutations: using start index (gives combinations, not permutations)

Evaluate expression: forgetting to handle consecutive digits as multi-digit numbers

Unique BSTs: not memoizing build(start,end) → exponential recomputation

On this page