CODING PATTERNS · LESSON 10 OF 28 · 26 MIN VIDEO · 8 PROBLEMS

Subsets

Module Progress (0 / 8 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (26 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Subsets — How the Pattern Works

The Subsets (Combinatorial Tree Enumeration) pattern constructs all valid subsets, permutations, Cartesian combinations, or rule-constrained sequences by modeling sequential item or position choices as levels of a decision tree. Whether expanded breadth-first (iteratively cascading partial results level by level) or depth-first via backtracking, each root-to-node path encodes a unique choice vector so every valid output is built once without post-hoc set deduplication. Early constraint pruning and duplicate-control invariants cut invalid or redundant subtrees immediately, reducing brute-force generate-and-filter work (such as O(n * n^n) slot trials or O(n * 4^n) unfiltered bracket strings) to complexity proportional to the valid output set.

WHEN TO USE THIS PATTERN
  • The prompt asks to list all subsets, combinations, permutations, or valid arrangements—or to count distinct sequences—rather than finding a single extremum.
  • Input dimensions are small (typically n <= 15–20 for subsets/combinations or n <= 8–10 for permutations), signaling exponential O(2^n) or factorial O(n!) output sizes.
  • Solutions decompose into one discrete choice per item or position: include/exclude, character case toggle, keypad letter mapping, or gap insertion.
  • The input contains duplicate elements while outputs must be unique, calling for sorted last-layer cascading or frequency-counter backtracking.
COMMON INTERVIEW PITFALLS
  • Appending directly to result while iterating over result without slicing or staging into a temporary grown list, causing an infinite loop as newly added subsets are re-extended in the same pass.
  • Forgetting to sort nums before checking nums[i] == nums[i - 1] in duplicate-subset enumeration, or branching per duplicate index rather than per unique value in tile/permutation counting.
  • Returning [""] instead of [] on empty input when problems like Letter Combinations of a Phone Number define zero positions as yielding zero combinations.
  • Pruning branches with total + x > k when the input can contain zero or negative integers; monotonic upper-bound sum pruning requires strictly positive (or non-negative) remaining elements.
Iterative Cascading (BFS Include / Exclude)Generating the power set of distinct elements or position-by-position expansions iteratively without recursion overhead.
def subsets_cascading(nums):
    result = [[]]
    for x in nums:
        grown = [curr + [x] for curr in result]
        result += grown
    return result
Sorted Duplicate-Safe CascadingGenerating distinct subsets from inputs with duplicates by restricting repeated values to extend only the subsets added in the immediately preceding step.
def subsets_with_dup(nums):
    nums = sorted(nums)
    result, start_new = [[]], 0
    for i, x in enumerate(nums):
        start = start_new if (i > 0 and x == nums[i - 1]) else 0
        start_new = len(result)
        for s in result[start:start_new]:
            result.append(s + [x])
    return result
Pruned Backtracking (State-Space DFS)Generating rule-constrained sequences or counting distinct arrangements over character frequencies while cutting invalid branches immediately.
def pruned_backtrack(n):
    result = []
    def grow(state, opened, closed):
        if len(state) == 2 * n:
            result.append(state)
            return
        if opened < n:
            grow(state + "(", opened + 1, closed)
        if closed < opened:
            grow(state + ")", opened, closed + 1)
    grow("", 0, 0)
    return result

01. Subsets

Optimal Target: O(n · 2ⁿ) time and space

Given an integer array nums of distinct elements, return all possible subsets (the power set) in any order without duplicate subsets.

EXAMPLE 1
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Explanation: Starting from [[]], processing 1 yields [[], [1]], processing 2 doubles to [[], [1], [2], [1, 2]], and processing 3 doubles again to all 8 subsets.
ARCHITECTURE / DATA FLOW DIAGRAM
[][][1][][2][1][1,2][][3][2][2,3][1][1,3][1,2][1,2,3]123
AUTOMATED TEST SUITE
Test Case 1
Input: [1, 2, 3]
Expected: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Test Case 2
Input: []
Expected: [[]]
Test Case 3
Input: [4, 5]
Expected: [[], [4], [5], [4, 5]]
Pattern Trigger Hint ("How to Spot It")

every selection → include or exclude, item by item

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute subsets against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

You have four items. How many subsets can you make, counting the empty one?