Backtracking — Permutations
↗ LeetCode: Permutations · Medium · pattern chapter →
Asked atMetaAmazonGoogleMicrosoftBloombergApple
Return all permutations of distinct integers.
Example 1 — nums=[1,2,3] → 6 permutations Example 2 — nums=[1] → [[1]]
Constraints — 1 ≤ n ≤ 6. Brute checks all n^n placements: at n=8 that's ~10⁷ ops. Backtracking with used-mask visits exactly n! = 40320 at n=8; grows to 3·10⁶ at n=10.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Insert-at-every-position recursion
Build permutations of length k+1 by inserting the (k+1)-th element into every position of length-k perms.
Approach 2 — Swap-in-place (canonical)
Insight. At depth k, swap each remaining candidate into position k, recurse, swap back.
java
List<List<Integer>> permute(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
dfs(nums, 0, out);
return out;
}
void dfs(int[] a, int k, List<List<Integer>> out) {
if (k == a.length) {
List<Integer> p = new ArrayList<>();
for (int x : a) p.add(x);
out.add(p); return;
}
for (int i = k; i < a.length; i++) {
swap(a, k, i);
dfs(a, k + 1, out);
swap(a, k, i);
}
}
void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n · n!); Space O(n).
Approach 3 — Used-set + build (extensible to duplicates)
Cleaner when duplicates exist — see Permutations II.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Insert-at-position | O(n · n!) | O(n · n!) | works |
| Swap-in-place | O(n · n!) | O(n) | canonical |
| Used set | O(n · n!) | O(n) | dup-friendly |
When to use which
- Standard interview → swap-in-place.
- Duplicates → used-set variant.
- Kth permutation → factorial-number system, no enumeration.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems