Backtracking Permutations: Can You Trace the Recursion Stack?

Originally published on LeetCopilot Blog

---

If you can't see how the stack grows and unwinds, duplicates creep in and base cases fire wrong. Here's how to visualize it.

Permutation problems expose every weakness in backtracking discipline. If you cannot see how the recursion stack grows and unwinds, duplicates creep in, base cases fire too early, and your explanation feels shaky. This guide walks through a trace you can picture, plus a repeatable checklist to narrate calmly in interviews.

TL;DR

• The primary task is to visualize each call as a stack frame containing path, used[], and remaining choices.
• It matters for interviews because clear narration of backtracking states proves you control branching rather than guessing.
• Core steps: define the state, pick a candidate, recurse, undo the pick, and track duplicates with a visited set per depth.
• Beginners often forget to mark elements before recursing or fail to unmark, causing missing or repeated permutations.
• You will learn a table-style trace, a safe code template, and quick pruning rules to keep the recursion tree tidy.

Beginner-Friendly Explanation: What the Stack Holds

• State: Current path (chosen elements), used[] boolean flags, and the input array.
• Action: Pick an unused element, append to path, recurse, then backtrack by popping and unmarking.
• Base case: When path.length === nums.length, emit a permutation.
• Why visuals help: Seeing frames side by side prevents double-picks and clarifies why we undo work on the way back up.

If you prefer a diagram-first walkthrough, skim Draw a Recursion Tree for Backtracking String Problems and apply the same labeling habit to permutations.

Step-by-Step Learning Guidance

1) Label the frame

Write down path, used, and choices for each call. This mirrors the state-labeling advice in How to Spot Overlapping Subproblems Before Writing DP, but for backtracking the emphasis is on which options remain.

2) Choose, recurse, undo

• Choose a candidate that is not marked in used.
• Recurse with the updated path.
• Undo: pop the element and unmark it before trying the next candidate.

3) Guard against duplicates

For inputs with repeated numbers, track a depth-local set so the same value is not chosen twice at the same level. This mirrors the pruning mindset from How to Choose Between BFS and DFS on LeetCode, where the structure dictates safe moves.

4) Narrate as you go

Practice saying: “At depth d, path is X, options are Y; I pick Z, mark it, recurse, then unmark.” Tools like LeetCopilot can mirror that narration by showing a side-by-side stack so you notice missed unmarks early.

Visualizable Example: Tracing [1, 1, 2]

Frame | path | used       | depth-local seen
----- | ---- | ---------- | ----------------
0     | []   | [F, F, F]  | {}
1     | [1]  | [T, F, F]  | {1}
2     | [1,1]| [T, T, F]  | {1}
3     | [1,1,2]| [T,T,T]  | { }

Notice how the seen set resets each depth, preventing the second 1 at frame 1 but allowing it at frame 2.

Code Example: Safe Permutation Backtracking Template

def permute_unique(nums):
    nums.sort()
    used = [False] * len(nums)
    path, result = [], []

    def dfs():
        if len(path) == len(nums):
            result.append(path.copy())
            return
        prev = None
        for i, val in enumerate(nums):
            if used[i] or val == prev:
                continue
            used[i] = True
            path.append(val)
            dfs()
            path.pop()
            used[i] = False
            prev = val

    dfs()
    return result

The prev variable enforces the depth-local duplicate rule seen in the table.

Practical Preparation Strategies

• Trace tiny arrays: Work through [1,2], [1,1,2], and [1,2,3] by hand before coding.
• Speak the undo step: Say “pop and unmark” aloud to avoid leaving used in the wrong state.
• Compare DFS/BFS thinking: Revisit When to Use BFS vs DFS in Binary Tree Interviews to solidify when deep-first exploration is appropriate.
• Use guided hints sparingly: A helper like LeetCopilot can flag forgotten unmarks without handing over the full solution, reinforcing disciplined tracing.

Common Mistakes to Avoid

Mistake 1: Forgetting to unmark

Leaving used[i] as true blocks later branches and silently drops permutations.

Mistake 2: Sorting without duplicate control

Sorting alone is insufficient; you must also skip repeated values per depth.

Mistake 3: Mutating shared arrays

Modifying the input array during recursion can corrupt sibling branches. Stick to path and used.

Mistake 4: Early base-case return

Returning after the first full permutation stops exploration. Always backtrack and continue the loop.

FAQ

• How do I know the depth-local set is correct? If two equal values appear at the same depth without distinct indices, you should skip the later one.
• What should I practice first? Start with [1,2] then [1,1,2], narrating each push/pop.
• Is this important for interviews? Yes—permutation and combination generators are common, and interviewers listen for disciplined state management.
• How do I debug quickly? Log path and used before and after recursion to spot missing undo steps.

Conclusion

Tracing the recursion stack makes backtracking predictable instead of mystical. By labeling state, enforcing depth-local duplicate checks, and speaking the undo step, you can generate permutations confidently. Keep the trace habit, and your interview explanations will match the clarity of your code.

---

If you're looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.