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 46

Permutations (LeetCode 46)

Target Frequency:MetaAmazonGoogle

Given an array nums of distinct integers, return every possible ordering of all its elements -- i.e., every permutation -- in any order.

A permutation uses each element from nums exactly once, arranged into some linear sequence.

Worked Examples

Example 1
Input:nums = [1,2,3]
Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Explanation: Three distinct numbers can be ordered in 3 * 2 * 1 = 6 ways.
Example 2
Input:nums = [0,1]
Output:[[0,1],[1,0]]
Explanation: Two numbers can be ordered in two ways.
Example 3
Input:nums = [1]
Output:[[1]]
Explanation: A single number has one ordering.

⚖️Formal Constraints & Bounds

  • 1 <= nums.length <= 6

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

  • All the integers of nums are unique.

Deep-Dive & Conceptual Insights

Core Insight

A permutation uses every element, only reordering them -- unlike a subset, which may leave elements out. Because an earlier element may still be needed later, a used set (not a start index) tracks which elements are currently placed; both path and used must be reverted together on backtrack.

Real-World Scenario & Production Applications

Scheduling every possible ordering of a fixed set of tasks on a single machine, or enumerating every seating arrangement at a table, both require generating every permutation of a small fixed set.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Unused Element Candidate Selection

Iterate through all elements in nums and branch on candidates that have not yet been used in the active permutation (not used[i]).

Mathematical Recurrence / Code Invariant
for i in range(len(nums)):
    if not used[i]:

Step-by-Step Execution Trace Table

Code / Blueprint
                                       [ ] (Root, used={}, d=0)
                         /                        |                        \
             choose 1   /             choose 2    |             choose 3    \
                       /                          |                          \
                 [ 1 ] (d=1)                 [ 2 ] (d=1)                 [ 3 ] (d=1)
                /           \               /           \               /           \
       choose 2/   choose 3  \     choose 1/   choose 3  \     choose 1/   choose 2  \
              /               \           /               \           /               \
           [1,2] (d=2)       [1,3] (d=2)[2,1] (d=2)       [2,3] (d=2)[3,1] (d=2)       [3,2] (d=2)
             |                 |         |                 |         |                 |
     choose 3|         choose 2| choose 3|         choose 1| choose 2|         choose 1|
             v                 v         v                 v         v                 v
          [1,2,3] ✅        [1,3,2] ✅[2,1,3] ✅        [2,3,1] ✅[3,1,2] ✅        [3,2,1] ✅
 
Step-by-Step Decision Trace (for nums = [1, 2, 3])
  1. Step 1 (Root, d=0): path = [], used = {}. Loop available candidates [1, 2, 3].
  2. Step 2 (Choose 1, d=1): path = [1], used = {1}. Loop candidates [1, 2, 3] (1 in used →\rightarrow→ skip).
  3. Step 3 (Branch Left: Choose 2, d=2): path = [1, 2], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
  4. Step 4 (Choose 3, d=3): path = [1, 2, 3], used = {1, 2, 3}. Base Case (len == 3): Record [1, 2, 3] ✅ (#1).
  5. Step 5 (Backtrack / Pop 3, d=2): path = [1, 2], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  6. Step 6 (Backtrack / Pop 2, d=1): path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2). Next candidate: 3.
  7. Step 7 (Branch Right: Choose 3, d=2): path = [1, 3], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
  8. Step 8 (Choose 2, d=3): path = [1, 3, 2], used = {1, 2, 3}. Base Case (len == 3): Record [1, 3, 2] ✅ (#2).
  9. Step 9 (Backtrack / Pop 2, d=2): path = [1, 3], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
  10. Step 10 (Backtrack / Pop 3, d=1): path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  11. Step 11 (Backtrack / Pop 1, d=0): path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 1). Next candidate: 2.
  12. Step 12 (Choose 2, d=1): path = [2], used = {2}. Loop candidates [1, 2, 3] (2 in used →\rightarrow→ skip).
  13. Step 13 (Branch Left: Choose 1, d=2): path = [2, 1], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
  14. Step 14 (Choose 3, d=3): path = [2, 1, 3], used = {1, 2, 3}. Base Case (len == 3): Record [2, 1, 3] ✅ (#3).
  15. Step 15 (Backtrack / Pop 3, d=2): path = [2, 1], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  16. Step 16 (Backtrack / Pop 1, d=1): path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 3.
  17. Step 17 (Branch Right: Choose 3, d=2): path = [2, 3], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
  18. Step 18 (Choose 1, d=3): path = [2, 3, 1], used = {1, 2, 3}. Base Case (len == 3): Record [2, 3, 1] ✅ (#4).
  19. Step 19 (Backtrack / Pop 1, d=2): path = [2, 3], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
  20. Step 20 (Backtrack / Pop 3, d=1): path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  21. Step 21 (Backtrack / Pop 2, d=0): path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 2). Next candidate: 3.
  22. Step 22 (Choose 3, d=1): path = [3], used = {3}. Loop candidates [1, 2, 3] (3 in used →\rightarrow→ skip).
  23. Step 23 (Branch Left: Choose 1, d=2): path = [3, 1], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
  24. Step 24 (Choose 2, d=3): path = [3, 1, 2], used = {1, 2, 3}. Base Case (len == 3): Record [3, 1, 2] ✅ (#5).
  25. Step 25 (Backtrack / Pop 2, d=2): path = [3, 1], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
  26. Step 26 (Backtrack / Pop 1, d=1): path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 2.
  27. Step 27 (Branch Right: Choose 2, d=2): path = [3, 2], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
  28. Step 28 (Choose 1, d=3): path = [3, 2, 1], used = {1, 2, 3}. Base Case (len == 3): Record [3, 2, 1] ✅ (#6).
  29. Step 29 (Backtrack / Pop 1, d=2): path = [3, 2], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
  30. Step 30 (Backtrack / Pop 2, d=1): path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
  31. Step 31 (Backtrack / Pop 3, d=0): path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 3). All 6 permutations generated! Search Complete: Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
Full Walkthrough31 Steps
Input:nums = [1,2,3]Expected:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1🌱 ROOT(Root, d=0)
path = []
Choices:1 2 3
path = [], used = {}. Loop available candidates [1, 2, 3].
2🟢 CHOOSE(Choose 1, d=1)
path = [1]
Choices:1 ✓ 2 3
path = [1], used = {1}. Loop candidates [1, 2, 3] (1 in used →\rightarrow→ skip).
3🟢 CHOOSE(Branch Left: Choose 2, d=2)
path = [1, 2]
Choices:1 2 ✓ 3
path = [1, 2], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
4✅ RECORD / GOAL(Choose 3, d=3)
path = [1, 2, 3]
path = [1, 2, 3], used = {1, 2, 3}. Base Case (len == 3): Record [1, 2, 3] ✅ (#1).
5↩️ BACKTRACK / POP(Backtrack / Pop 3, d=2)
path = [1, 2]
path = [1, 2], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
6↩️ BACKTRACK / POP(Backtrack / Pop 2, d=1)
path = [1]
path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2). Next candidate: 3.
7🟢 CHOOSE(Branch Right: Choose 3, d=2)
path = [1, 3]
Choices:1 2 3 ✓
path = [1, 3], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
8✅ RECORD / GOAL(Choose 2, d=3)
path = [1, 3, 2]
path = [1, 3, 2], used = {1, 2, 3}. Base Case (len == 3): Record [1, 3, 2] ✅ (#2).
9↩️ BACKTRACK / POP(Backtrack / Pop 2, d=2)
path = [1, 3]
path = [1, 3], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
10↩️ BACKTRACK / POP(Backtrack / Pop 3, d=1)
path = [1]
path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
11🌱 ROOT(Backtrack / Pop 1, d=0)
path = []
path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 1). Next candidate: 2.
12🟢 CHOOSE(Choose 2, d=1)
path = [2]
Choices:1 2 ✓ 3
path = [2], used = {2}. Loop candidates [1, 2, 3] (2 in used →\rightarrow→ skip).
13🟢 CHOOSE(Branch Left: Choose 1, d=2)
path = [2, 1]
Choices:1 ✓ 2 3
path = [2, 1], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
14✅ RECORD / GOAL(Choose 3, d=3)
path = [2, 1, 3]
path = [2, 1, 3], used = {1, 2, 3}. Base Case (len == 3): Record [2, 1, 3] ✅ (#3).
15↩️ BACKTRACK / POP(Backtrack / Pop 3, d=2)
path = [2, 1]
path = [2, 1], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
16↩️ BACKTRACK / POP(Backtrack / Pop 1, d=1)
path = [2]
path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 3.
17🟢 CHOOSE(Branch Right: Choose 3, d=2)
path = [2, 3]
Choices:1 2 3 ✓
path = [2, 3], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
18✅ RECORD / GOAL(Choose 1, d=3)
path = [2, 3, 1]
path = [2, 3, 1], used = {1, 2, 3}. Base Case (len == 3): Record [2, 3, 1] ✅ (#4).
19↩️ BACKTRACK / POP(Backtrack / Pop 1, d=2)
path = [2, 3]
path = [2, 3], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
20↩️ BACKTRACK / POP(Backtrack / Pop 3, d=1)
path = [2]
path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
21🌱 ROOT(Backtrack / Pop 2, d=0)
path = []
path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 2). Next candidate: 3.
22🟢 CHOOSE(Choose 3, d=1)
path = [3]
Choices:1 2 3 ✓
path = [3], used = {3}. Loop candidates [1, 2, 3] (3 in used →\rightarrow→ skip).
23🟢 CHOOSE(Branch Left: Choose 1, d=2)
path = [3, 1]
Choices:1 ✓ 2 3
path = [3, 1], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
24✅ RECORD / GOAL(Choose 2, d=3)
path = [3, 1, 2]
path = [3, 1, 2], used = {1, 2, 3}. Base Case (len == 3): Record [3, 1, 2] ✅ (#5).
25↩️ BACKTRACK / POP(Backtrack / Pop 2, d=2)
path = [3, 1]
path = [3, 1], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
26↩️ BACKTRACK / POP(Backtrack / Pop 1, d=1)
path = [3]
path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 2.
27🟢 CHOOSE(Branch Right: Choose 2, d=2)
path = [3, 2]
Choices:1 2 ✓ 3
path = [3, 2], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
28✅ RECORD / GOAL(Choose 1, d=3)
path = [3, 2, 1]
path = [3, 2, 1], used = {1, 2, 3}. Base Case (len == 3): Record [3, 2, 1] ✅ (#6).
29↩️ BACKTRACK / POP(Backtrack / Pop 1, d=2)
path = [3, 2]
path = [3, 2], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
30↩️ BACKTRACK / POP(Backtrack / Pop 2, d=1)
path = [3]
path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
31🌱 ROOT(Backtrack / Pop 3, d=0)
path = []
path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 3). All 6 permutations generated! Search Complete: Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
Code Shape
Archetype Code Shape
Python
1results, path, used = [], [], [False] * len(nums)
2def backtrack():
3 if len(path) == len(nums):
4 results.append(list(path))
5 return
6 for i in range(len(nums)):
7 if used[i]:
8 continue
9 used[i] = True
10 path.append(nums[i])
11 backtrack()
12 path.pop()
13 used[i] = False
14backtrack()
15return results

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Every backtracking archetype so far used a start index to avoid reusing earlier elements — but [1,2] and [2,1] are different permutations, so "only look forward from where I left off" is actively wrong here.

📚 The Analogy: Arranging Books on a Shelf

Imagine arranging three books on a shelf, one slot at a time. For the first slot, you can pick any of the three books — there's no "start" restricting you to some subset. Once a book is placed, it's physically on the shelf and can't be picked again for a later slot — so you keep a mental note of "already placed" books, and skip over them each time you scan your full collection for the next slot.

🔑 The Key Idea in the Code

Two pieces of state get chosen and un-chosen together (path and used[i]) — forgetting to revert either one leaves the recursion in a corrupted state for every sibling branch that runs afterward.

  • Using linear scan if num in path (O(N)O(N)O(N) lookup): Checking membership in a list takes O(N)O(N)O(N) time per step. Use a boolean used array or in-place swapping nums[start], nums[i] = nums[i], nums[start] to achieve O(1)O(1)O(1) checks.

  • Forgetting to undo in-place swap: When using the swap method, failing to swap back nums[start], nums[i] = nums[i], nums[start] after recursion corrupts array order for sibling branches.

  • Appending without shallow copy: Appending path instead of path[:] stores references that get cleared upon backtrack.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

The statement asks for "all the possible permutations" of an array of "distinct integers", with at most 6 of them: order matters and every element is used exactly once, so drop start, loop from 0 every time, and skip a position whose used[i] is true.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: path holds the elements chosen so far, in order, and used[i] is true exactly when nums[i] is in path. Position i is choosable only while used[i] is false. Complete when len(path) == len(nums).

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

  • Appending live path reference to results: results.append(path) appends a mutable reference; when backtracking pops elements, the recorded result becomes empty. Always append a copy: results.append(list(path)) or path[:].

  • Using a start index instead of used[i] -- permutations can place an earlier-in-the-list element after a later one (e.g. choosing 1 after 2), which a forward-only start index forbids.

  • Undoing only path (pop) but not used[i] = False -- the code still looks symmetric, but the mark leaks into sibling branches.

  • Off-by-one on the completion check -- len(path) == len(nums), not len(path) == len(nums) - 1.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I'd use Permutations. Any position of the ordering may hold any element that is not already in path, so the loop always starts at index 0 and skips i when used[i] is true. For each other i, I set used[i] to True, append nums[i], call backtrack, then pop and set used[i] back to False. Because every choice is undone after its branch, each full path is a different sequence of choices, and with distinct values a different ordering, so I save every ordering exactly once when path is as long as nums. The trap is the undo: if I forget used[i] = False after the call, every later branch still treats that element as taken, and for [1, 2, 3] I get only [[1, 2, 3]]. There are N! orderings, each copied in O(N), so it's O(N times N!) time, and O(N) extra space for path, used and the recursion, not counting the output."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N! · N)

Look at the recursive decision tree: At depth 0, we choose from N elements. At depth 1, we choose from N-1 elements. At depth k, we choose from N-k elements. The decision tree branches into exactly N · (N-1) · (N-2) · ... · 1 = N! leaf states. At each of the N! leaf states, we make a deep copy list(path) of length N to append to results, which takes O(N) time per leaf. Multiplying N! leaves by O(N) copy cost gives total O(N! · N) time.

SPACE COMPLEXITY

O(N) Call Stack

Look at memory allocation: The recursive call stack descends to maximum depth N before hitting a base case and returning (O(N) stack frames). The mutable list path holds at most N elements, and the boolean lookup array used uses N entries. Excluding the output list results (which holds N! permutations of size N), auxiliary memory is strictly O(N).

Formal Recurrence Relation

T(N) = N! · O(N)

Derivation Progression

Factorial Decision Tree

N! leaf permutation states

Branching factor starts at N and decrements at each depth, creating N! total permutation leaves.

Leaf Snapshot Copying

O(N) list(path) deep copy

When path reaches length N, copying path into results takes O(N) time.

Total Time

O(N! · N)

N! leaves multiplied by O(N) snapshot work per leaf yields strictly O(N! · N) time.

Variable Definitions

NNN

Number of elements in the input array

Memory Architecture & Bounds

🟣 Call Stack

O(N) Recursion call stack of maximum depth N

🔵 Auxiliary Heap

O(N) path list of length N and boolean used array of size N

🟢 Output Space

O(N! · N) Result list storing all N! permutations

Boundary Best / Worst Cases

Best Case

O(N!⋅N)O(N! · N)O(N!⋅N)

Average Case

O(N!⋅N)O(N! · N)O(N!⋅N)

Worst Case

O(N!⋅N)O(N! · N)O(N!⋅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: "all possible permutations", "distinct integers". State-tracking via boolean used array: every position in the permutation can select any unused number from the input.

CONSTRAINTS & BOUNDS

1≤nums.length≤6  ⟹  6!=7201 \le nums.length \le 6 \implies 6! = 7201≤nums.length≤6⟹6!=720 leaves.

FAANG PRODUCTION TRAPS & EDGE CASES

Using start index: permutations must inspect elements before i as well, so do NOT use start.

Theory Context•Backtracking & State Search
MediumLC 46

Permutations (LeetCode 46)

Target Frequency:MetaAmazonGoogle

Given an array nums of distinct integers, return every possible ordering of all its elements -- i.e., every permutation -- in any order.

A permutation uses each element from nums exactly once, arranged into some linear sequence.

Worked Examples

Example 1
Input:nums = [1,2,3]
Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Explanation: Three distinct numbers can be ordered in 3 * 2 * 1 = 6 ways.
Example 2
Input:nums = [0,1]
Output:[[0,1],[1,0]]
Explanation: Two numbers can be ordered in two ways.
Example 3
Input:nums = [1]
Output:[[1]]
Explanation: A single number has one ordering.

⚖️Formal Constraints & Bounds

  • 1 <= nums.length <= 6

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

  • All the integers of nums are unique.

Deep-Dive & Conceptual Insights

Core Insight

A permutation uses every element, only reordering them -- unlike a subset, which may leave elements out. Because an earlier element may still be needed later, a used set (not a start index) tracks which elements are currently placed; both path and used must be reverted together on backtrack.

Real-World Scenario & Production Applications

Scheduling every possible ordering of a fixed set of tasks on a single machine, or enumerating every seating arrangement at a table, both require generating every permutation of a small fixed set.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Unused Element Candidate Selection

Iterate through all elements in nums and branch on candidates that have not yet been used in the active permutation (not used[i]).

Mathematical Recurrence / Code Invariant
for i in range(len(nums)):
    if not used[i]:

Step-by-Step Execution Trace Table

Code / Blueprint
                                       [ ] (Root, used={}, d=0)
                         /                        |                        \
             choose 1   /             choose 2    |             choose 3    \
                       /                          |                          \
                 [ 1 ] (d=1)                 [ 2 ] (d=1)                 [ 3 ] (d=1)
                /           \               /           \               /           \
       choose 2/   choose 3  \     choose 1/   choose 3  \     choose 1/   choose 2  \
              /               \           /               \           /               \
           [1,2] (d=2)       [1,3] (d=2)[2,1] (d=2)       [2,3] (d=2)[3,1] (d=2)       [3,2] (d=2)
             |                 |         |                 |         |                 |
     choose 3|         choose 2| choose 3|         choose 1| choose 2|         choose 1|
             v                 v         v                 v         v                 v
          [1,2,3] ✅        [1,3,2] ✅[2,1,3] ✅        [2,3,1] ✅[3,1,2] ✅        [3,2,1] ✅
 
Step-by-Step Decision Trace (for nums = [1, 2, 3])
  1. Step 1 (Root, d=0): path = [], used = {}. Loop available candidates [1, 2, 3].
  2. Step 2 (Choose 1, d=1): path = [1], used = {1}. Loop candidates [1, 2, 3] (1 in used →\rightarrow→ skip).
  3. Step 3 (Branch Left: Choose 2, d=2): path = [1, 2], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
  4. Step 4 (Choose 3, d=3): path = [1, 2, 3], used = {1, 2, 3}. Base Case (len == 3): Record [1, 2, 3] ✅ (#1).
  5. Step 5 (Backtrack / Pop 3, d=2): path = [1, 2], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  6. Step 6 (Backtrack / Pop 2, d=1): path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2). Next candidate: 3.
  7. Step 7 (Branch Right: Choose 3, d=2): path = [1, 3], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
  8. Step 8 (Choose 2, d=3): path = [1, 3, 2], used = {1, 2, 3}. Base Case (len == 3): Record [1, 3, 2] ✅ (#2).
  9. Step 9 (Backtrack / Pop 2, d=2): path = [1, 3], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
  10. Step 10 (Backtrack / Pop 3, d=1): path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  11. Step 11 (Backtrack / Pop 1, d=0): path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 1). Next candidate: 2.
  12. Step 12 (Choose 2, d=1): path = [2], used = {2}. Loop candidates [1, 2, 3] (2 in used →\rightarrow→ skip).
  13. Step 13 (Branch Left: Choose 1, d=2): path = [2, 1], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
  14. Step 14 (Choose 3, d=3): path = [2, 1, 3], used = {1, 2, 3}. Base Case (len == 3): Record [2, 1, 3] ✅ (#3).
  15. Step 15 (Backtrack / Pop 3, d=2): path = [2, 1], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  16. Step 16 (Backtrack / Pop 1, d=1): path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 3.
  17. Step 17 (Branch Right: Choose 3, d=2): path = [2, 3], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
  18. Step 18 (Choose 1, d=3): path = [2, 3, 1], used = {1, 2, 3}. Base Case (len == 3): Record [2, 3, 1] ✅ (#4).
  19. Step 19 (Backtrack / Pop 1, d=2): path = [2, 3], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
  20. Step 20 (Backtrack / Pop 3, d=1): path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
  21. Step 21 (Backtrack / Pop 2, d=0): path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 2). Next candidate: 3.
  22. Step 22 (Choose 3, d=1): path = [3], used = {3}. Loop candidates [1, 2, 3] (3 in used →\rightarrow→ skip).
  23. Step 23 (Branch Left: Choose 1, d=2): path = [3, 1], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
  24. Step 24 (Choose 2, d=3): path = [3, 1, 2], used = {1, 2, 3}. Base Case (len == 3): Record [3, 1, 2] ✅ (#5).
  25. Step 25 (Backtrack / Pop 2, d=2): path = [3, 1], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
  26. Step 26 (Backtrack / Pop 1, d=1): path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 2.
  27. Step 27 (Branch Right: Choose 2, d=2): path = [3, 2], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
  28. Step 28 (Choose 1, d=3): path = [3, 2, 1], used = {1, 2, 3}. Base Case (len == 3): Record [3, 2, 1] ✅ (#6).
  29. Step 29 (Backtrack / Pop 1, d=2): path = [3, 2], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
  30. Step 30 (Backtrack / Pop 2, d=1): path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
  31. Step 31 (Backtrack / Pop 3, d=0): path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 3). All 6 permutations generated! Search Complete: Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
Full Walkthrough31 Steps
Input:nums = [1,2,3]Expected:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1🌱 ROOT(Root, d=0)
path = []
Choices:1 2 3
path = [], used = {}. Loop available candidates [1, 2, 3].
2🟢 CHOOSE(Choose 1, d=1)
path = [1]
Choices:1 ✓ 2 3
path = [1], used = {1}. Loop candidates [1, 2, 3] (1 in used →\rightarrow→ skip).
3🟢 CHOOSE(Branch Left: Choose 2, d=2)
path = [1, 2]
Choices:1 2 ✓ 3
path = [1, 2], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
4✅ RECORD / GOAL(Choose 3, d=3)
path = [1, 2, 3]
path = [1, 2, 3], used = {1, 2, 3}. Base Case (len == 3): Record [1, 2, 3] ✅ (#1).
5↩️ BACKTRACK / POP(Backtrack / Pop 3, d=2)
path = [1, 2]
path = [1, 2], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
6↩️ BACKTRACK / POP(Backtrack / Pop 2, d=1)
path = [1]
path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2). Next candidate: 3.
7🟢 CHOOSE(Branch Right: Choose 3, d=2)
path = [1, 3]
Choices:1 2 3 ✓
path = [1, 3], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
8✅ RECORD / GOAL(Choose 2, d=3)
path = [1, 3, 2]
path = [1, 3, 2], used = {1, 2, 3}. Base Case (len == 3): Record [1, 3, 2] ✅ (#2).
9↩️ BACKTRACK / POP(Backtrack / Pop 2, d=2)
path = [1, 3]
path = [1, 3], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
10↩️ BACKTRACK / POP(Backtrack / Pop 3, d=1)
path = [1]
path = [1], used = {1} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
11🌱 ROOT(Backtrack / Pop 1, d=0)
path = []
path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 1). Next candidate: 2.
12🟢 CHOOSE(Choose 2, d=1)
path = [2]
Choices:1 2 ✓ 3
path = [2], used = {2}. Loop candidates [1, 2, 3] (2 in used →\rightarrow→ skip).
13🟢 CHOOSE(Branch Left: Choose 1, d=2)
path = [2, 1]
Choices:1 ✓ 2 3
path = [2, 1], used = {1, 2}. Loop candidates [1, 2, 3] (1, 2 in used →\rightarrow→ skip).
14✅ RECORD / GOAL(Choose 3, d=3)
path = [2, 1, 3]
path = [2, 1, 3], used = {1, 2, 3}. Base Case (len == 3): Record [2, 1, 3] ✅ (#3).
15↩️ BACKTRACK / POP(Backtrack / Pop 3, d=2)
path = [2, 1]
path = [2, 1], used = {1, 2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
16↩️ BACKTRACK / POP(Backtrack / Pop 1, d=1)
path = [2]
path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 3.
17🟢 CHOOSE(Branch Right: Choose 3, d=2)
path = [2, 3]
Choices:1 2 3 ✓
path = [2, 3], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
18✅ RECORD / GOAL(Choose 1, d=3)
path = [2, 3, 1]
path = [2, 3, 1], used = {1, 2, 3}. Base Case (len == 3): Record [2, 3, 1] ✅ (#4).
19↩️ BACKTRACK / POP(Backtrack / Pop 1, d=2)
path = [2, 3]
path = [2, 3], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
20↩️ BACKTRACK / POP(Backtrack / Pop 3, d=1)
path = [2]
path = [2], used = {2} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 3).
21🌱 ROOT(Backtrack / Pop 2, d=0)
path = []
path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 2). Next candidate: 3.
22🟢 CHOOSE(Choose 3, d=1)
path = [3]
Choices:1 2 3 ✓
path = [3], used = {3}. Loop candidates [1, 2, 3] (3 in used →\rightarrow→ skip).
23🟢 CHOOSE(Branch Left: Choose 1, d=2)
path = [3, 1]
Choices:1 ✓ 2 3
path = [3, 1], used = {1, 3}. Loop candidates [1, 2, 3] (1, 3 in used →\rightarrow→ skip).
24✅ RECORD / GOAL(Choose 2, d=3)
path = [3, 1, 2]
path = [3, 1, 2], used = {1, 2, 3}. Base Case (len == 3): Record [3, 1, 2] ✅ (#5).
25↩️ BACKTRACK / POP(Backtrack / Pop 2, d=2)
path = [3, 1]
path = [3, 1], used = {1, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
26↩️ BACKTRACK / POP(Backtrack / Pop 1, d=1)
path = [3]
path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1). Next candidate: 2.
27🟢 CHOOSE(Branch Right: Choose 2, d=2)
path = [3, 2]
Choices:1 2 ✓ 3
path = [3, 2], used = {2, 3}. Loop candidates [1, 2, 3] (2, 3 in used →\rightarrow→ skip).
28✅ RECORD / GOAL(Choose 1, d=3)
path = [3, 2, 1]
path = [3, 2, 1], used = {1, 2, 3}. Base Case (len == 3): Record [3, 2, 1] ✅ (#6).
29↩️ BACKTRACK / POP(Backtrack / Pop 1, d=2)
path = [3, 2]
path = [3, 2], used = {2, 3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 1).
30↩️ BACKTRACK / POP(Backtrack / Pop 2, d=1)
path = [3]
path = [3], used = {3} →\rightarrow→ ↩️ BACKTRACK / POP (unmark 2).
31🌱 ROOT(Backtrack / Pop 3, d=0)
path = []
path = [], used = {} →\rightarrow→ ↩️ BACKTRACK / POP to Root (unmark 3). All 6 permutations generated! Search Complete: Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
Code Shape
Archetype Code Shape
Python
1results, path, used = [], [], [False] * len(nums)
2def backtrack():
3 if len(path) == len(nums):
4 results.append(list(path))
5 return
6 for i in range(len(nums)):
7 if used[i]:
8 continue
9 used[i] = True
10 path.append(nums[i])
11 backtrack()
12 path.pop()
13 used[i] = False
14backtrack()
15return results

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Every backtracking archetype so far used a start index to avoid reusing earlier elements — but [1,2] and [2,1] are different permutations, so "only look forward from where I left off" is actively wrong here.

📚 The Analogy: Arranging Books on a Shelf

Imagine arranging three books on a shelf, one slot at a time. For the first slot, you can pick any of the three books — there's no "start" restricting you to some subset. Once a book is placed, it's physically on the shelf and can't be picked again for a later slot — so you keep a mental note of "already placed" books, and skip over them each time you scan your full collection for the next slot.

🔑 The Key Idea in the Code

Two pieces of state get chosen and un-chosen together (path and used[i]) — forgetting to revert either one leaves the recursion in a corrupted state for every sibling branch that runs afterward.

  • Using linear scan if num in path (O(N)O(N)O(N) lookup): Checking membership in a list takes O(N)O(N)O(N) time per step. Use a boolean used array or in-place swapping nums[start], nums[i] = nums[i], nums[start] to achieve O(1)O(1)O(1) checks.

  • Forgetting to undo in-place swap: When using the swap method, failing to swap back nums[start], nums[i] = nums[i], nums[start] after recursion corrupts array order for sibling branches.

  • Appending without shallow copy: Appending path instead of path[:] stores references that get cleared upon backtrack.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

The statement asks for "all the possible permutations" of an array of "distinct integers", with at most 6 of them: order matters and every element is used exactly once, so drop start, loop from 0 every time, and skip a position whose used[i] is true.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: path holds the elements chosen so far, in order, and used[i] is true exactly when nums[i] is in path. Position i is choosable only while used[i] is false. Complete when len(path) == len(nums).

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

  • Appending live path reference to results: results.append(path) appends a mutable reference; when backtracking pops elements, the recorded result becomes empty. Always append a copy: results.append(list(path)) or path[:].

  • Using a start index instead of used[i] -- permutations can place an earlier-in-the-list element after a later one (e.g. choosing 1 after 2), which a forward-only start index forbids.

  • Undoing only path (pop) but not used[i] = False -- the code still looks symmetric, but the mark leaks into sibling branches.

  • Off-by-one on the completion check -- len(path) == len(nums), not len(path) == len(nums) - 1.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I'd use Permutations. Any position of the ordering may hold any element that is not already in path, so the loop always starts at index 0 and skips i when used[i] is true. For each other i, I set used[i] to True, append nums[i], call backtrack, then pop and set used[i] back to False. Because every choice is undone after its branch, each full path is a different sequence of choices, and with distinct values a different ordering, so I save every ordering exactly once when path is as long as nums. The trap is the undo: if I forget used[i] = False after the call, every later branch still treats that element as taken, and for [1, 2, 3] I get only [[1, 2, 3]]. There are N! orderings, each copied in O(N), so it's O(N times N!) time, and O(N) extra space for path, used and the recursion, not counting the output."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N! · N)

Look at the recursive decision tree: At depth 0, we choose from N elements. At depth 1, we choose from N-1 elements. At depth k, we choose from N-k elements. The decision tree branches into exactly N · (N-1) · (N-2) · ... · 1 = N! leaf states. At each of the N! leaf states, we make a deep copy list(path) of length N to append to results, which takes O(N) time per leaf. Multiplying N! leaves by O(N) copy cost gives total O(N! · N) time.

SPACE COMPLEXITY

O(N) Call Stack

Look at memory allocation: The recursive call stack descends to maximum depth N before hitting a base case and returning (O(N) stack frames). The mutable list path holds at most N elements, and the boolean lookup array used uses N entries. Excluding the output list results (which holds N! permutations of size N), auxiliary memory is strictly O(N).

Formal Recurrence Relation

T(N) = N! · O(N)

Derivation Progression

Factorial Decision Tree

N! leaf permutation states

Branching factor starts at N and decrements at each depth, creating N! total permutation leaves.

Leaf Snapshot Copying

O(N) list(path) deep copy

When path reaches length N, copying path into results takes O(N) time.

Total Time

O(N! · N)

N! leaves multiplied by O(N) snapshot work per leaf yields strictly O(N! · N) time.

Variable Definitions

NNN

Number of elements in the input array

Memory Architecture & Bounds

🟣 Call Stack

O(N) Recursion call stack of maximum depth N

🔵 Auxiliary Heap

O(N) path list of length N and boolean used array of size N

🟢 Output Space

O(N! · N) Result list storing all N! permutations

Boundary Best / Worst Cases

Best Case

O(N!⋅N)O(N! · N)O(N!⋅N)

Average Case

O(N!⋅N)O(N! · N)O(N!⋅N)

Worst Case

O(N!⋅N)O(N! · N)O(N!⋅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: "all possible permutations", "distinct integers". State-tracking via boolean used array: every position in the permutation can select any unused number from the input.

CONSTRAINTS & BOUNDS

1≤nums.length≤6  ⟹  6!=7201 \le nums.length \le 6 \implies 6! = 7201≤nums.length≤6⟹6!=720 leaves.

FAANG PRODUCTION TRAPS & EDGE CASES

Using start index: permutations must inspect elements before i as well, so do NOT use start.

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