Backtracking · LC #46
Permutations
Use a boolean used[] array to track which elements are in the current permutation. At each level try every unused element; backtrack by unmarking.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array `nums` of distinct integers, return all possible permutations.
Sample I/O
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Input: nums = [0,1] Output: [[0,1],[1,0]]
Intuition
How to Think About It
Intuition
Unlike combinations, permutations can reuse any position for any unused element. A boolean visited array marks which elements are "in play." At each level, we try all n elements - but skip already-used ones.
Core Concept
bt(curr): if curr.length == n, record. For i in 0..n-1: if used[i] skip. Mark used[i]=true, push nums[i], recurse, pop, mark used[i]=false. Records at leaves only.
When to use
Generate all orderings; anagram generation; arrange n items in all possible sequences.
When NOT to use
n > 8-10 (n! blows up); when you only need count (n!); when duplicates exist (Permutations II - LC 47).
Key Insights
What to Know Cold
- Key difference from subsets/combinations: loop always starts at 0 (not start), but uses visited[] to skip used elements.
- No start index - each position can take any unused element.
- n! leaves, each of depth n → O(n * n!) total work.
- The visited array is the state that separates this from combination problems.
- Alternative: swap-based approach avoids visited array but is harder to reason about.
1 example
Worked Examples
All arrangements of [1,2,3]
Generate all 6 permutations of [1,2,3].
Backtracking with used[] boolean array.
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Arrangement and scheduling problems (seat assignment, task ordering) reduce to permutation enumeration.