Hi👋SpeedAlgo • Deliberate Practice & Cognitive Ergonomics for Software Engineers

An interactive algorithm mastery and technical interview preparation platform published by Hi👋WebEnterprise. Built for senior and staff software engineers preparing for rigorous coding screens at top tech companies (FAANG/MAMAA).

13 Core Algorithmic Patterns & 225 Practice Problems

  • 1. Two Pointers (16 Paradigms, 43 Problems): Opposite ends, sorted pair sums, palindrome verification, trapping rain water, 3Sum, container with most water — includes the Sliding Window and Fast & Slow Pointers paradigms (contiguous subarray invariants, longest substrings, Floyd's cycle detection, linked list middle).
  • 2. Binary Search (9 Paradigms, 14 Problems): Monotonic predicate partitioning (feasible(x)), boundary search, rotated sorted arrays, square roots, minimum ship capacity, median of two sorted arrays, matrix median on value range.
  • 3. Bit Manipulation (5 Paradigms, 11 Problems): Counting set bits, XOR cancellation, bit reversal, bitmask pairing, maximum XOR with a bitwise trie.
  • 4. Math & Geometry (8 Paradigms, 14 Problems): Sieve of Eratosthenes, integer/roman conversions, modular arithmetic, geometric simulation.
  • 5. Tree/Graph Depth-First Search (15 Paradigms, 24 Problems): Path sums, lowest common ancestor, tree diameter, validating BSTs, tree DP (House Robber III, Binary Tree Cameras).
  • 6. Tree/Graph Breadth-First Search (5 Paradigms, 12 Problems): Level-order traversals, shortest path in unweighted graphs, zig-zag traversals, rotting oranges, word ladders.
  • 7. Graphs (12 Paradigms, 22 Problems): Topological sort, cycle detection, Dijkstra's algorithm, bipartite graph validation, network delay.
  • 8. Backtracking (6 Paradigms, 14 Problems): Subsets, permutations, combinations, constraint satisfaction, pruning, N-Queens, Sudoku solver.
  • 9. Dynamic Programming (13 Paradigms, 28 Problems): Memoization vs tabulation, 0/1 knapsack, unbounded knapsack, coin change, edit distance, longest common subsequence.
  • 10. Heap / Priority Queue (9 Paradigms, 11 Problems): Running medians, top-k elements, interval scheduling, IPO, k-way merges.
  • 11. Advanced Data Structures (7 Paradigms, 17 Problems): Trie (prefix tree), Union-Find (Disjoint Set Union), LRU Cache, LFU Cache, range-sum queries with updates.
  • 12. Stack (5 Paradigms, 9 Problems): Next greater element, largest rectangle in histogram, remove k digits, decode string, min stack.
  • 13. Intervals & Greedy (2 Paradigms, 6 Problems): Merge intervals, interval scheduling, meeting rooms by sweep line, jump game.

4-Stage Deliberate Practice Framework

  1. Stage 1 (Compare & Learn): Read the pattern's mental model, loop invariant and Big-O proof, compare the pattern's template with the problem's solution side by side, and use the step-by-step debugger. The solution can also be shown in C#, Java, TypeScript, C++, Go or Rust for almost every problem.
  2. Stage 2 (Active Recall): Rebuild the solution from memory in a code editor, with an invariant checklist and optional progressive hints, and check it against a judged test suite.
  3. Stage 3 (AI Interview Coach, coming soon): A mock-interview stage still in development; for now, students go straight from Stage 2 to Stage 4.
  4. Stage 4 (Solve on Your Own): Solve a new problem on your own against a 15-minute timer; your code is graded against a test suite. Python and TypeScript run in your browser and C# runs on our server (design problems grade in Python and TypeScript).

Equipped with a spaced-repetition review hub on a fixed 7-step schedule (1 day up to 90 days), a two-pane Studio workspace, and study notes.

Pricing, Access & Commercial Terms

  • Core Curriculum: 100% Free. No credit card required.
  • Coins: New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins.
  • AI Coach: Each AI coach question costs 1-5 coins, priced by the server according to its size.
  • BYOK (Bring Your Own Key): AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK).
  • Extras: Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1).
  • Payments & Refunds: Nothing on the site is sold for money: coins can only be earned, never bought. There are no subscriptions or charges, so there is nothing to refund.
  • Platform Operator: Hi👋WebEnterprise. Support & policies at hispeedalgo.com.
Skip to main content
Hi👋SpeedAlgo

Invariant-First Algorithmic Mastery

Arena
238Items
Theory Context•Backtracking & State Search
MediumLC 90

Subsets II (LeetCode 90)

Target Frequency:MetaAmazon

Given an integer array nums that may hold duplicate values, produce the full power set -- every possible subset, including the empty subset and the full array itself.

Because nums can repeat values, two different index choices might describe the same subset of values; the returned list must not contain that subset twice. Return the subsets in any order.

Worked Examples

Example 1
Input:nums = [1,2,2]
Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: Picking the first 2 or the second 2 gives the same subset, so [2] and [1,2] appear only once.
Example 2
Input:nums = [0]
Output:[[],[0]]
Explanation: A single element has two subsets: the empty one and itself.

⚖️Formal Constraints & Bounds

  • 1 <= nums.length <= 10

  • -10 <= nums[i] <= 10

Deep-Dive & Conceptual Insights
🌳Decision Tree • Sibling Deduplication (nums = [1, 2, 2])
Recorded (6)Pruned (2)
d=0d=1d=2d=3+1+2skip 2+2skip 2+2+2Root: [][1][2]✂️ Prune nums[2]=2[1, 2]✂️ Prune nums[2]=2[2, 2][1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Prune Guard: if i > start and nums[i] == nums[i-1]: continue

Core Insight

The horizontal duplicate prune if i > start and nums[i] == nums[i-1]: continue skips identical sibling choices at the same recursion depth.

Real-World Scenario & Production Applications

Feature flag combinations testing and database query optimization filter permutations.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Universal Node Snapshot (Every Prefix Valid)

Because every node in the decision tree represents a valid subset, record a deep copy list(path) immediately on entry to every recursive frame.

Mathematical Recurrence / Code Invariant
def dfs(start):
    # Every decision tree node is a valid subset
    results.append(list(path))

Step-by-Step Execution Trace Table

Code / Blueprint
                         [ ] (Root, ✅ Record [])
                      /           |             \
           choose 1  /  choose 2  |    choose 2  \ (i=2 > start=0 & nums[2]==nums[1])
                    /   (i=1)     |              \
             [ 1 ] ✅             [ 2 ] ✅        ✂️ PRUNED (Duplicate Sibling)
            /     \                  |
 choose 2  /       \ choose 2 (i=2)   | choose 2 (i=2)
          /         \ (i>start dup)  |
      [ 1, 2 ] ✅   ✂️ PRUNED       [ 2, 2 ] ✅
         |
 choose 2| (i=2)
         |
    [ 1, 2, 2 ] ✅
 
Step-by-Step Decision Trace
  1. Step 1 (Root, d=0): path = [] →\rightarrow→ Record [] ✅. Loop i ∈ [0..2].
  2. Step 2 (Choose nums[0]=1, d=1): path = [1] →\rightarrow→ Record [1] ✅. Recurse with start=1.
  3. Step 3 (Choose nums[1]=2, d=2): path = [1, 2] →\rightarrow→ Record [1, 2] ✅. Recurse with start=2.
  4. Step 4 (Choose nums[2]=2, d=3): path = [1, 2, 2] →\rightarrow→ Record [1, 2, 2] ✅. Loop at start=3 empty.
  5. Step 5 (Backtrack / Pop nums[2], d=2): path = [1, 2]. Loop at d=2 exhausted.
  6. Step 6 (Backtrack / Pop nums[1], d=1): path = [1]. Loop at d=1 moves to i=2.
  7. Step 7 (Candidate nums[2]=2, d=2): i=2 > start=1 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling).
  8. Step 8 (Backtrack / Pop nums[0], d=0): path = []. Root loop moves to i=1.
  9. Step 9 (Choose nums[1]=2, d=1): path = [2] →\rightarrow→ Record [2] ✅. Recurse with start=2.
  10. Step 10 (Choose nums[2]=2, d=2): path = [2, 2] →\rightarrow→ Record [2, 2] ✅. Loop at start=3 empty.
  11. Step 11 (Backtrack / Pop nums[2], d=1): path = [2].
  12. Step 12 (Backtrack / Pop nums[1], d=0): path = []. Root loop moves to i=2.
  13. Step 13 (Candidate nums[2]=2, d=1): i=2 > start=0 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling). Search Complete: 6 unique subsets recorded.
Full Walkthrough13 Steps
Input:nums = [1,2,2]Expected:[[],[1],[1,2],[1,2,2],[2],[2,2]]
1🌱 ROOT(Root, d=0)
path = []
path = [] →\rightarrow→ Record [] ✅. Loop i ∈ [0..2].
2✅ RECORD / GOAL(Choose nums[0]=1, d=1)
path = [1]
path = [1] →\rightarrow→ Record [1] ✅. Recurse with start=1.
3✅ RECORD / GOAL(Choose nums[1]=2, d=2)
path = [1, 2]
path = [1, 2] →\rightarrow→ Record [1, 2] ✅. Recurse with start=2.
4✅ RECORD / GOAL(Choose nums[2]=2, d=3)
path = [1, 2, 2]
path = [1, 2, 2] →\rightarrow→ Record [1, 2, 2] ✅. Loop at start=3 empty.
5↩️ BACKTRACK / POP(Backtrack / Pop nums[2], d=2)
path = [1, 2]
path = [1, 2]. Loop at d=2 exhausted.
6↩️ BACKTRACK / POP(Backtrack / Pop nums[1], d=1)
path = [1]
path = [1]. Loop at d=1 moves to i=2.
7✂️ PRUNED(Candidate nums[2]=2, d=2)
i=2 > start=1 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling).
8🌱 ROOT(Backtrack / Pop nums[0], d=0)
path = []
path = []. Root loop moves to i=1.
9✅ RECORD / GOAL(Choose nums[1]=2, d=1)
path = [2]
path = [2] →\rightarrow→ Record [2] ✅. Recurse with start=2.
10✅ RECORD / GOAL(Choose nums[2]=2, d=2)
path = [2, 2]
path = [2, 2] →\rightarrow→ Record [2, 2] ✅. Loop at start=3 empty.
11↩️ BACKTRACK / POP(Backtrack / Pop nums[2], d=1)
path = [2]
path = [2].
12🌱 ROOT(Backtrack / Pop nums[1], d=0)
path = []
path = []. Root loop moves to i=2.
13✂️ PRUNED(Candidate nums[2]=2, d=1)
i=2 > start=0 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling). Search Complete: 6 unique subsets recorded.
Code Shape
Archetype Code Shape
Python
1nums.sort(), results = [], path = []
2def backtrack(start):
3 results.append(list(path))
4 for i in range(start, len(nums)):
5 if i > start and nums[i] == nums[i-1]:
6 continue
7 path.append(nums[i])
8 backtrack(i + 1)
9 path.pop()
10backtrack(0)
11return results

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

[1,1,2] naively produces duplicate subsets like [1] twice — once from each 1. Sorting first, then adding one guard clause, eliminates every duplicate without ever generating and filtering them.

👯 The Analogy: Twins Standing in Line, Only the First Answers the Question

Sort the array so identical values become adjacent, like twins standing next to each other in a line. At any given fork in the decision tree, ask: "should I skip this next value?" If two twins are standing side by side and the first twin already got a turn deciding "should I include this number" at this exact fork, the second identical twin doesn't need to answer the same question again — they'd get an identical answer, producing an identical (duplicate) subset. So only the first twin in each identical run gets asked at that fork; every later twin defers.

🔑 The Key Idea in the Code

The i > start check is crucial: it only skips a duplicate if it's a sibling at the same recursion level, not a duplicate value chosen at a deeper level — [1,1] (both twins included together) is still a valid, distinct subset.

🔑 The Key Takeaway

The i > start condition is the key part of this pattern. It guarantees that you can use duplicate numbers from the input array to build a sequence (parent-to-child depth), but it absolutely prevents you from using identical numbers to start duplicate parallel branches (sibling width).

If the loop at Depth 0 had moved on to i = 1, trying to start a brand new combination with the second 1, then i > start (1 > 0) would be True, and it would successfully skip the duplicate sibling branch.

  • Skipping duplicates without sorting: Sibling duplicate detection nums[i] == nums[i-1] requires identical numbers to be adjacent. Forgetting nums.sort() produces duplicate subsets.

  • Using i > 0 instead of i > start: Guarding duplicate check with if nums[i] == nums[i-1]: without i > start prunes valid identical elements across different recursion levels (e.g. [2, 2] cannot be formed).

  • Deduplicating post-hoc with set: Casting subset lists to tuples to store in a hash set wastes memory and time; pruning at the branch level guarantees zero duplicate branches explored.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

The statement asks for "all possible subsets (the power set)", says nums "may contain duplicates" and that the answer "must not contain duplicate subsets", and caps nums.length at 10. Every subset is wanted and the input repeats values: Subsets, with sibling deduplication.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: path always holds exactly the choices from the root to the current node, and is put back to its pre-call state before backtrack returns. Every node (not just a leaf) is a valid subset, so backtrack saves a copy of path on entry, not only at a base case.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

  • Writing i > 0 instead of i > start in the skip: it also skips the second 1 one level deeper, so [1, 1] is lost.

  • Forgetting to sort before the nums[i] == nums[i - 1] check -- it only catches duplicates that sit next to each other.

  • Deduplicating with a set of results instead of skipping at the branch -- pays the full 2^N cost and then filters.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I'd use Subsets. Every node of the decision tree is a valid subset, so backtrack(start) saves a copy of path as soon as it is entered, including the empty one at the root. The loop only picks indices from start onward, so each subset is built in one order and is never produced twice as a reordering. The input can hold duplicates, so I sort it first to put equal values next to each other. Then, inside the loop, I skip nums[i] when i > start and it equals nums[i - 1], because that value was already tried at this level of the tree. The trap is writing i > 0 instead of i > start: that also skips the second 1 when it is picked one level deeper, so for [1, 1, 2] I would lose [1, 1] and [1, 1, 2]. There are up to 2^N subsets, each copied in O(N), so it's O(N times 2^N) time, with O(N) recursion stack."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(2^N · N)

Look at the execution steps: Sorting takes O(N log N). Backtracking explores 2^N subsets, skipping duplicates via if i > start and nums[i] == nums[i-1]: continue. Copying each subset takes O(N).

SPACE COMPLEXITY

O(N) Call Stack

Recursion stack depth equals N; path array has size <= N.

Formal Recurrence Relation

T(N) = O(N log N) + 2^N · O(N) = O(2^N · N)

Derivation Progression

Sorting Pass

O(N log N)

Groups duplicate elements adjacent in array.

One Call per Subset

at most 2^N calls

Each call of backtrack saves one subset and loops over the later indices, so there is one call per distinct subset: at most 2^N calls, each copying up to N values.

Variable Definitions

NNN

Number of elements in the input array

Memory Architecture & Bounds

🟣 Call Stack

O(N) Call stack depth

🔵 Auxiliary Heap

O(N) Current subset path buffer

🟢 Output Space

O(2^N · N) Array of all subsets

Boundary Best / Worst Cases

Best Case

O(N2)O(N^2)O(N2) when every value is equal: only N + 1 distinct subsets, copied at up to N each

Average Case

O(2N⋅N)O(2^N · N)O(2N⋅N)

Worst Case

O(2N⋅N)O(2^N · N)O(2N⋅N)

Decision & State-Space Search Tree

Decision & State-Space Search Tree
Synthesizing vector architecture diagram...
Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "subsets with duplicates", "solution set must not contain duplicate subsets". Sibling deduplication via sorting: when identical numbers are grouped adjacent to each other, you can cleanly skip duplicate choices at the same tree depth.

CONSTRAINTS & BOUNDS

1≤nums.length≤101 \le nums.length \le 101≤nums.length≤10, values [−10,10][-10, 10][−10,10]. Power set size ≤210=1024\le 2^{10} = 1024≤210=1024.

FAANG PRODUCTION TRAPS & EDGE CASES

Memory fails before time: up to 2N2^N2N subsets of up to NNN values each is O(N⋅2N)O(N \cdot 2^N)O(N⋅2N) output, over 33 million lists at N=25N = 25N=25. When the caller only iterates, stream the subsets with a generator instead of building the list, and yield a copy, since path keeps changing after the yield.

Theory Context•Backtracking & State Search
MediumLC 90

Subsets II (LeetCode 90)

Target Frequency:MetaAmazon

Given an integer array nums that may hold duplicate values, produce the full power set -- every possible subset, including the empty subset and the full array itself.

Because nums can repeat values, two different index choices might describe the same subset of values; the returned list must not contain that subset twice. Return the subsets in any order.

Worked Examples

Example 1
Input:nums = [1,2,2]
Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: Picking the first 2 or the second 2 gives the same subset, so [2] and [1,2] appear only once.
Example 2
Input:nums = [0]
Output:[[],[0]]
Explanation: A single element has two subsets: the empty one and itself.

⚖️Formal Constraints & Bounds

  • 1 <= nums.length <= 10

  • -10 <= nums[i] <= 10

Deep-Dive & Conceptual Insights
🌳Decision Tree • Sibling Deduplication (nums = [1, 2, 2])
Recorded (6)Pruned (2)
d=0d=1d=2d=3+1+2skip 2+2skip 2+2+2Root: [][1][2]✂️ Prune nums[2]=2[1, 2]✂️ Prune nums[2]=2[2, 2][1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Prune Guard: if i > start and nums[i] == nums[i-1]: continue

Core Insight

The horizontal duplicate prune if i > start and nums[i] == nums[i-1]: continue skips identical sibling choices at the same recursion depth.

Real-World Scenario & Production Applications

Feature flag combinations testing and database query optimization filter permutations.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Universal Node Snapshot (Every Prefix Valid)

Because every node in the decision tree represents a valid subset, record a deep copy list(path) immediately on entry to every recursive frame.

Mathematical Recurrence / Code Invariant
def dfs(start):
    # Every decision tree node is a valid subset
    results.append(list(path))

Step-by-Step Execution Trace Table

Code / Blueprint
                         [ ] (Root, ✅ Record [])
                      /           |             \
           choose 1  /  choose 2  |    choose 2  \ (i=2 > start=0 & nums[2]==nums[1])
                    /   (i=1)     |              \
             [ 1 ] ✅             [ 2 ] ✅        ✂️ PRUNED (Duplicate Sibling)
            /     \                  |
 choose 2  /       \ choose 2 (i=2)   | choose 2 (i=2)
          /         \ (i>start dup)  |
      [ 1, 2 ] ✅   ✂️ PRUNED       [ 2, 2 ] ✅
         |
 choose 2| (i=2)
         |
    [ 1, 2, 2 ] ✅
 
Step-by-Step Decision Trace
  1. Step 1 (Root, d=0): path = [] →\rightarrow→ Record [] ✅. Loop i ∈ [0..2].
  2. Step 2 (Choose nums[0]=1, d=1): path = [1] →\rightarrow→ Record [1] ✅. Recurse with start=1.
  3. Step 3 (Choose nums[1]=2, d=2): path = [1, 2] →\rightarrow→ Record [1, 2] ✅. Recurse with start=2.
  4. Step 4 (Choose nums[2]=2, d=3): path = [1, 2, 2] →\rightarrow→ Record [1, 2, 2] ✅. Loop at start=3 empty.
  5. Step 5 (Backtrack / Pop nums[2], d=2): path = [1, 2]. Loop at d=2 exhausted.
  6. Step 6 (Backtrack / Pop nums[1], d=1): path = [1]. Loop at d=1 moves to i=2.
  7. Step 7 (Candidate nums[2]=2, d=2): i=2 > start=1 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling).
  8. Step 8 (Backtrack / Pop nums[0], d=0): path = []. Root loop moves to i=1.
  9. Step 9 (Choose nums[1]=2, d=1): path = [2] →\rightarrow→ Record [2] ✅. Recurse with start=2.
  10. Step 10 (Choose nums[2]=2, d=2): path = [2, 2] →\rightarrow→ Record [2, 2] ✅. Loop at start=3 empty.
  11. Step 11 (Backtrack / Pop nums[2], d=1): path = [2].
  12. Step 12 (Backtrack / Pop nums[1], d=0): path = []. Root loop moves to i=2.
  13. Step 13 (Candidate nums[2]=2, d=1): i=2 > start=0 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling). Search Complete: 6 unique subsets recorded.
Full Walkthrough13 Steps
Input:nums = [1,2,2]Expected:[[],[1],[1,2],[1,2,2],[2],[2,2]]
1🌱 ROOT(Root, d=0)
path = []
path = [] →\rightarrow→ Record [] ✅. Loop i ∈ [0..2].
2✅ RECORD / GOAL(Choose nums[0]=1, d=1)
path = [1]
path = [1] →\rightarrow→ Record [1] ✅. Recurse with start=1.
3✅ RECORD / GOAL(Choose nums[1]=2, d=2)
path = [1, 2]
path = [1, 2] →\rightarrow→ Record [1, 2] ✅. Recurse with start=2.
4✅ RECORD / GOAL(Choose nums[2]=2, d=3)
path = [1, 2, 2]
path = [1, 2, 2] →\rightarrow→ Record [1, 2, 2] ✅. Loop at start=3 empty.
5↩️ BACKTRACK / POP(Backtrack / Pop nums[2], d=2)
path = [1, 2]
path = [1, 2]. Loop at d=2 exhausted.
6↩️ BACKTRACK / POP(Backtrack / Pop nums[1], d=1)
path = [1]
path = [1]. Loop at d=1 moves to i=2.
7✂️ PRUNED(Candidate nums[2]=2, d=2)
i=2 > start=1 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling).
8🌱 ROOT(Backtrack / Pop nums[0], d=0)
path = []
path = []. Root loop moves to i=1.
9✅ RECORD / GOAL(Choose nums[1]=2, d=1)
path = [2]
path = [2] →\rightarrow→ Record [2] ✅. Recurse with start=2.
10✅ RECORD / GOAL(Choose nums[2]=2, d=2)
path = [2, 2]
path = [2, 2] →\rightarrow→ Record [2, 2] ✅. Loop at start=3 empty.
11↩️ BACKTRACK / POP(Backtrack / Pop nums[2], d=1)
path = [2]
path = [2].
12🌱 ROOT(Backtrack / Pop nums[1], d=0)
path = []
path = []. Root loop moves to i=2.
13✂️ PRUNED(Candidate nums[2]=2, d=1)
i=2 > start=0 and nums[2] == nums[1] →\rightarrow→ ✂️ PRUNE (Duplicate Sibling). Search Complete: 6 unique subsets recorded.
Code Shape
Archetype Code Shape
Python
1nums.sort(), results = [], path = []
2def backtrack(start):
3 results.append(list(path))
4 for i in range(start, len(nums)):
5 if i > start and nums[i] == nums[i-1]:
6 continue
7 path.append(nums[i])
8 backtrack(i + 1)
9 path.pop()
10backtrack(0)
11return results

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

[1,1,2] naively produces duplicate subsets like [1] twice — once from each 1. Sorting first, then adding one guard clause, eliminates every duplicate without ever generating and filtering them.

👯 The Analogy: Twins Standing in Line, Only the First Answers the Question

Sort the array so identical values become adjacent, like twins standing next to each other in a line. At any given fork in the decision tree, ask: "should I skip this next value?" If two twins are standing side by side and the first twin already got a turn deciding "should I include this number" at this exact fork, the second identical twin doesn't need to answer the same question again — they'd get an identical answer, producing an identical (duplicate) subset. So only the first twin in each identical run gets asked at that fork; every later twin defers.

🔑 The Key Idea in the Code

The i > start check is crucial: it only skips a duplicate if it's a sibling at the same recursion level, not a duplicate value chosen at a deeper level — [1,1] (both twins included together) is still a valid, distinct subset.

🔑 The Key Takeaway

The i > start condition is the key part of this pattern. It guarantees that you can use duplicate numbers from the input array to build a sequence (parent-to-child depth), but it absolutely prevents you from using identical numbers to start duplicate parallel branches (sibling width).

If the loop at Depth 0 had moved on to i = 1, trying to start a brand new combination with the second 1, then i > start (1 > 0) would be True, and it would successfully skip the duplicate sibling branch.

  • Skipping duplicates without sorting: Sibling duplicate detection nums[i] == nums[i-1] requires identical numbers to be adjacent. Forgetting nums.sort() produces duplicate subsets.

  • Using i > 0 instead of i > start: Guarding duplicate check with if nums[i] == nums[i-1]: without i > start prunes valid identical elements across different recursion levels (e.g. [2, 2] cannot be formed).

  • Deduplicating post-hoc with set: Casting subset lists to tuples to store in a hash set wastes memory and time; pruning at the branch level guarantees zero duplicate branches explored.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

The statement asks for "all possible subsets (the power set)", says nums "may contain duplicates" and that the answer "must not contain duplicate subsets", and caps nums.length at 10. Every subset is wanted and the input repeats values: Subsets, with sibling deduplication.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: path always holds exactly the choices from the root to the current node, and is put back to its pre-call state before backtrack returns. Every node (not just a leaf) is a valid subset, so backtrack saves a copy of path on entry, not only at a base case.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

  • Writing i > 0 instead of i > start in the skip: it also skips the second 1 one level deeper, so [1, 1] is lost.

  • Forgetting to sort before the nums[i] == nums[i - 1] check -- it only catches duplicates that sit next to each other.

  • Deduplicating with a set of results instead of skipping at the branch -- pays the full 2^N cost and then filters.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I'd use Subsets. Every node of the decision tree is a valid subset, so backtrack(start) saves a copy of path as soon as it is entered, including the empty one at the root. The loop only picks indices from start onward, so each subset is built in one order and is never produced twice as a reordering. The input can hold duplicates, so I sort it first to put equal values next to each other. Then, inside the loop, I skip nums[i] when i > start and it equals nums[i - 1], because that value was already tried at this level of the tree. The trap is writing i > 0 instead of i > start: that also skips the second 1 when it is picked one level deeper, so for [1, 1, 2] I would lose [1, 1] and [1, 1, 2]. There are up to 2^N subsets, each copied in O(N), so it's O(N times 2^N) time, with O(N) recursion stack."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(2^N · N)

Look at the execution steps: Sorting takes O(N log N). Backtracking explores 2^N subsets, skipping duplicates via if i > start and nums[i] == nums[i-1]: continue. Copying each subset takes O(N).

SPACE COMPLEXITY

O(N) Call Stack

Recursion stack depth equals N; path array has size <= N.

Formal Recurrence Relation

T(N) = O(N log N) + 2^N · O(N) = O(2^N · N)

Derivation Progression

Sorting Pass

O(N log N)

Groups duplicate elements adjacent in array.

One Call per Subset

at most 2^N calls

Each call of backtrack saves one subset and loops over the later indices, so there is one call per distinct subset: at most 2^N calls, each copying up to N values.

Variable Definitions

NNN

Number of elements in the input array

Memory Architecture & Bounds

🟣 Call Stack

O(N) Call stack depth

🔵 Auxiliary Heap

O(N) Current subset path buffer

🟢 Output Space

O(2^N · N) Array of all subsets

Boundary Best / Worst Cases

Best Case

O(N2)O(N^2)O(N2) when every value is equal: only N + 1 distinct subsets, copied at up to N each

Average Case

O(2N⋅N)O(2^N · N)O(2N⋅N)

Worst Case

O(2N⋅N)O(2^N · N)O(2N⋅N)

Decision & State-Space Search Tree

Decision & State-Space Search Tree
Synthesizing vector architecture diagram...
Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "subsets with duplicates", "solution set must not contain duplicate subsets". Sibling deduplication via sorting: when identical numbers are grouped adjacent to each other, you can cleanly skip duplicate choices at the same tree depth.

CONSTRAINTS & BOUNDS

1≤nums.length≤101 \le nums.length \le 101≤nums.length≤10, values [−10,10][-10, 10][−10,10]. Power set size ≤210=1024\le 2^{10} = 1024≤210=1024.

FAANG PRODUCTION TRAPS & EDGE CASES

Memory fails before time: up to 2N2^N2N subsets of up to NNN values each is O(N⋅2N)O(N \cdot 2^N)O(N⋅2N) output, over 33 million lists at N=25N = 25N=25. When the caller only iterates, stream the subsets with a generator instead of building the list, and yield a copy, since path keeps changing after the yield.

© 2026 Hi👋WebEnterprise. All rights reserved.
Sitemap•llms.txt•