LeetCode 46 Permutations: Master Backtracking with Three Solutions That Impress Interviewers
This article thoroughly explains LeetCode 46 Permutations as the foundational backtracking problem, covering standard used-array approach, in-place swap optimization, and bitmask technique with lowbit, plus complexity analysis, common pitfalls, and interview follow-up strategies.
Last month while screening candidates for algorithm interviews, the author asked the same LeetCode 46 Permutations question to four candidates in one day. All four wrote working solutions, but their skill levels were immediately apparent: some only memorized templates, some could explain the reasoning, and one produced a bitwise solution that stood out.
1. Clarify the Problem in 30 Seconds
Before coding, confirm key constraints:
Duplicate elements? How to ask: "Any duplicate numbers in array?" Answer: No duplicates (duplicates would be LC 47, different pruning)
Element range How to ask: "Only 1-9?" Answer: Arbitrary int, n ≤ 6
Output order How to ask: "Any order requirement?" Answer: Any order acceptable
Return type Answer: List<List<Integer>> This habit distinguishes template-memorizers from engineering-minded candidates.
2. Backtracking as Maze Traversal on Decision Tree
The essence of permutation: at each step pick one remaining number to fill the next position. Visualizing [1,2,3] as a decision tree shows 3! = 6 leaf nodes matching the six permutations.
Three core elements for any backtracking problem:
path — Choices made so far: Currently selected numbers list
choice list — What can be chosen now: Numbers where used[i] == false termination — When to collect result: path.size() == nums.length The soul of backtracking: make choice → recurse → undo choice . Undo must be strictly symmetric with choice; missing one leaks state and corrupts all subsequent paths because path and used are shared and reused across branches.
💡 Key analogy : backtracking's visited is a "resource lock, must return after use"; graph DFS's visited is a "flag planted forever". This is the essential difference: backtracking = DFS + state restoration .
Expanded trace of first two levels:
depth=0 path=[] used=[F,F,F] ┐
├─ pick 1 path=[1] used=[T,F,F] │ make choice
│ ├─ pick 2 path=[1,2] used=[T,T,F] │
│ │ └─ pick 3 → 🎉 collect [1,2,3] ┘
│ └─ backtrack path=[1] used=[T,F,F] ┐
├─ backtrack path=[] used=[F,F,F] ┘ undo choice3. Standard Solution: used[] + path
Preferred interview solution, most readable, extends smoothly to LC 47:
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, new ArrayList<>(), used, res);
return res;
}
private void backtrack(int[] nums, List<Integer> path,
boolean[] used, List<List<Integer>> res) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path)); // ⚠️ must copy!
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// make choice
used[i] = true;
path.add(nums[i]);
// recurse
backtrack(nums, path, used, res);
// undo choice (strictly symmetric)
path.remove(path.size() - 1);
used[i] = false;
}
}
}Pitfall 1: res.add(path) stores reference, all results become empty
Java collections store references. After adding path to res, later path.remove() mutates the same object — all references in res point to the eventually cleared list. Fix: res.add(new ArrayList<>(path)) deep-copies a snapshot.
Pitfall 2: Forgetting to undo turns permutations into garbage
Make-choice and undo-choice must appear in pairs as muscle memory:
// make choice ←→ undo choice (strictly symmetric!)
path.add(x); path.remove(path.size() - 1);
used[i] = true; used[i] = false;Mnemonic: "One in one out, one add one remove, one on one off. Forget undo, permutations turn to chaos." Order of the two undo lines doesn't affect correctness but reversing the make-choice order (stack-like) reduces omissions.
Pitfall 3: Using path.contains() for deduplication drops complexity a tier
Many beginners write if (path.contains(nums[i])) continue;. It passes but interviewer will ask: "Can you do O(1) deduplication?" Comparison: path.contains(x) — Single query: O(n) scan; Overall complexity: O(n² × n!) boolean[] used — Single query: O(1) index access; Overall complexity: O(n × n!) used[] is classic space-for-time; using it over contains signals constant-factor optimization awareness.
4. Bonus Solution: In-Place Swap
After used[] version, mention: "Actually can avoid marker array by swapping." Interviewer reaction usually changes 😏.
Core idea: maintain implicit boundary index — [0, index-1] is fixed prefix, [index, n-1] is candidate pool. Swap each candidate into index position (equivalent to choosing), recurse to index+1, swap back on return.
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>(factorial(nums.length));
backtrack(nums, 0, res);
return res;
}
private void backtrack(int[] nums, int first, List<List<Integer>> res) {
if (first == nums.length) {
List<Integer> one = new ArrayList<>(nums.length);
for (int x : nums) one.add(x);
res.add(one);
return;
}
for (int i = first; i < nums.length; i++) {
swap(nums, first, i); // make choice: i-th element moves up
backtrack(nums, first + 1, res);
swap(nums, first, i); // undo: swap twice = perfect restore
}
}
private void swap(int[] a, int i, int j) {
if (i == j) return;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
private int factorial(int n) { int r = 1; while (n > 1) r *= n--; return r; }
}Eliminates used[] and path, auxiliary space only recursion stack O(n). Two notes: (1) double swap is the undo, satisfying symmetry; (2) modifies original array order (final order not guaranteed restored, results not lexicographic) — if caller cares, copy beforehand or document side effect.
5. Killer Solution: Bitmask
If swap is "excellent", bitmask "widens the gap". Fewer than 5% of candidates produce this live.
Idea: use an int 's binary bits instead of boolean[]; bit i = 1 means nums[i] used:
class Solution {
private int[] nums;
private int n;
private final List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
this.n = nums.length;
dfs(0, 0, new int[n]); // mask: bit i = 1 means nums[i] used
return ans;
}
private void dfs(int mask, int depth, int[] path) {
if (depth == n) {
List<Integer> one = new ArrayList<>(n);
for (int x : path) one.add(x);
ans.add(one);
return;
}
int available = ((1 << n) - 1) ^ mask; // 🌟 complement → all selectable bits
while (available != 0) {
int bit = available & -available; // 🌟 lowbit: extract lowest 1
int i = Integer.numberOfTrailingZeros(bit); // 🌟 bit → index, O(1)
path[depth] = nums[i];
dfs(mask | bit, depth + 1, path); // ✅ no undo needed: mask/depth passed by value
available ^= bit; // clear this bit, enumerate next
}
}
}🔥 Highlight breakdown (recite these four points in interview) : x & -x is classic lowbit trick, extracts lowest set bit in one step; Integer.numberOfTrailingZeros is JDK's hardware-instruction-level implementation, faster than manual loop; mask and depth passed by value — each frame naturally owns its state — completely eliminates "forgot to undo" bugs ; Limitation: n ≤ 31 (int bits), but problem has n ≤ 6 so plenty of room.
6. Choosing Among Three Approaches
Extra Space : used[] + path — O(n); In-Place Swap — O(1) (excl. recursion stack); Bitmask — O(n) ( path array)
Readability : used[] + path — ⭐⭐⭐⭐⭐; In-Place Swap — ⭐⭐⭐⭐; Bitmask — ⭐⭐⭐
Modifies Input? : used[] + path — ❌; In-Place Swap — ⚠️ Yes; Bitmask — ❌
Extend to LC 47 (duplicates) : used[] + path — ✅ Sort + prune; In-Place Swap — ⚠️ Pruning more complex; Bitmask — ⚠️ Bit-level dedup trickier
Interview Bonus : used[] + path — Pass/Good; In-Place Swap — Excellent; Bitmask — Impressive
Recommended Scenario : used[] + path — Interview default stable choice ; In-Place Swap — Space-optimal pursuit; Bitmask — Show bitwise mastery
Advice: interview — start with used[] for safe pass, then proactively offer swap as space optimization, then bitmask if confident. Pacing matters; leading with bitmask risks tangling yourself and losing points.
7. Complexity Analysis: Already Theoretically Optimal
Time : O(n × n!) — n! leaf nodes (permutations), each solution copied to result in O(n)
Aux Space : O(n) — Recursion depth n + path + used array, all O(n)
Output Space : O(n × n!) — n! permutations × length n each
💬 Interview bonus line : "This problem's lower bound is O(n × n!) because just outputting results takes that much — already theoretically optimal , no faster algorithm exists." Saying this proactively beats waiting to be asked. Also separate "auxiliary space O(n)" from "output space O(n × n!)" — conflating them is a common articulation mistake.
8. Common Interview Follow-ups
Q1: Duplicate elements in array? (LC 47 Permutations II)
First Arrays.sort(nums) to group duplicates, then add one line in loop for same-level pruning :
if (used[i]) continue;
// 🌟 key: in same level, duplicate element only allows "first" to take effect
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;Most mis-explain the condition: it's !used[i-1], not used[i-1]. used[i-1] == false: previous duplicate was just undone in this level → its branch already explored → current branch would produce duplicate permutations — this is tree-level deduplication , prune it; used[i-1] == true: previous duplicate still on current recursion path → that's tree-branch duplication, which is valid, must not prune.
Tree-level pruning is more efficient because it cuts duplicate branches horizontally at the same level earlier; tree-branch pruning (when used[i-1] == true) goes deeper before cutting, doing more wasted work.
Q2: Can you do it without recursion?
Yes, use lexicographic order (next permutation, LC 31) iteratively: sort to get smallest permutation, repeatedly call nextPermutation until back to ascending order:
1,2,3 → 1,3,2 → 2,1,3 → 2,3,1 → 3,1,2 → 3,2,1 → back to ascending, stop 🔚Advantage: no recursion stack, memory controllable, suitable for "on-demand next" scenarios.
Q3: What if n = 10?
10! = 3,628,800— 3.6M permutations × 10 ints each → memory and output explode. That's why permutation problems usually cap n at 8-10.
Real engineering answer for large n isn't algorithmic micro-optimization but:
Ask if business truly needs full enumeration (usually not);
Switch to Iterator<List<Integer>> lazy streaming , produce and consume incrementally;
Need only k-th permutation? Use Cantor expansion O(n²) direct indexing, no enumeration needed.
Q4: Why doesn't backtracking use memoization like DP?
Backtracking solves " enumerate all solutions ", each branch path is an independent solution, no overlapping subproblems to reuse ; DP seeks optimal value or count, has massive overlapping subproblems, so memoization helps. One-liner: Backtracking is "exhaustive", DP is "deduplication" — different philosophies.
9. Pitfall Cheat Sheet (Save This)
1. Collecting reference — ❌ res.add(path) → all empty lists; ✅ res.add(new ArrayList<>(path)) deep copy snapshot
2. Forgot to undo — ❌ Cross-branch state pollution, wrong/missing results; ✅ Make/undo strictly paired as muscle memory; or bitmask value-passing cures it
3. Low-efficiency dedup — ❌ path.contains(x) O(n) each; ✅ boolean[] used or bitmask → O(1)
4. Duplicates produce duplicate results — ❌ Copy this code for LC 47 → duplicate permutations; ✅ LC 47: sort first, prune i>0 && nums[i]==nums[i-1] && !used[i-1] 5. Tree-level condition reversed — ❌ LC 47 mistakenly writes used[i-1] == true; ✅ Memorize: tree-level check false , tree-branch check true
6. OOM when n slightly larger — ❌ Stuff all into List at once; ✅ Use Iterator lazy generation / batch processing, produce and consume
7. Stack overflow deep recursion — ❌ Blind recursion; ✅ This problem n≤6 safe; general case use non-recursive (next-permutation iteration)
8. Mutated input array — ❌ In-place swap scrambles original; ✅ Copy beforehand, or explicitly document side effect
9. List frequent resizing — ❌ new ArrayList<>() no capacity hint; ✅ Pre-size to n! capacity, reduce array copy overhead
10. Turn One Problem into a Whole Class
Interview micro-habits that add points:
Draw the tree proactively on whiteboard — shows genuine understanding, not memorization;
Explain framework before coding : state the three backtracking elements (path, choice list, termination) so interviewer follows your rhythm;
Point out traps yourself : mention new ArrayList<>(path) before being asked;
Connect related problems : Subsets (LC 78), Combination Sum (LC 39), N-Queens (LC 51) are all variants of the same backtracking skeleton, only pruning conditions differ — that's one problem mastered, hundred problems mastered .
🔁 Backtracking Trio : path path + choice list used + termination. 🧠 Routine : make choice → recurse → undo choice, undo must be symmetric. ⚡ Bonus : swap used[] for bitmask, x & -x lowbit, value-passing naturally avoids undo. 📊 Complexity : time O(n × n!) (output lower bound), aux space O(n). 🚀 Extensions : LC 47 dedup via "sort + same-level prune", large n via "streaming / Cantor expansion".
Actionable advice: tonight, type all three versions once each, then rewrite LC 47's pruning from memory. Reading ten times beats writing once; once muscle memory forms, you'll finish the core solution in 5 minutes at interview, leaving the rest of the time to discuss extensions and demonstrate depth.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
