Permutations

Learning goal: Recognize permutations as a search over choices for each position.

Core idea A permutation is complete only when every input element has been placed exactly once. At the first position, any element is possible; after choosing one, only the remaining elements can fill the next position. This creates a branching decision tree whose leaves are the answers.

Algorithm plan

• Start with an empty path representing the current arrangement.
• Try each element that is not already used.
• Place it in the next position and recurse.
• Record a copy when path.length == nums.length.

Micro-example For [1,2,3], choosing 1 first fixes the prefix [1]. The next position can then choose 2 or 3, creating two sibling branches.

Pitfalls

• Do not reuse an element already in path.
• Record a copy of path, not the mutable working array itself.
• The order of generated answers may differ from the example.

Recap

• Every level fixes one position.
• Every leaf is one complete permutation.
• Distinct inputs make used membership unambiguous.

Learning goal: Understand why making and undoing choices explores every valid ordering.

Core idea Backtracking treats the partial permutation as state. A recursive call extends that state by one unused value; when the call returns, the value is removed so the caller can try a different sibling choice. The same array can therefore represent many branches without permanently contaminating later decisions.

Algorithm plan

backtrack(path, used):
    if path contains every element:
        save a copy of path
        return

    for each index i:
        if used[i]:
            continue
        used[i] = true
        append nums[i] to path
        backtrack(path, used)
        remove last item from path
        used[i] = false

The used[] array answers whether an element is already present in the current branch. The two undo operations restore the exact state that existed before the recursive call.

Micro-example After building [1,2,3], return to [1,2]: unmark 3, then remove it. Now the algorithm can return to [1] and try 3 in the second position.

Pitfalls

• Mark before recursing and unmark after recursing.
• Remove the last path item, not an arbitrary value.
• Pass or maintain state consistently at every depth.

Recap

• Choose, recurse, undo is the backtracking pattern.
• used[] prevents duplicate use within one branch.
• Undo restores sibling branches to a clean state.

Learning goal: Translate the backtracking idea into a correct implementation and justify its completeness.

Core idea At recursion depth k, the algorithm has already fixed positions 0 through k - 1. It tries every unused input index for position k, so no legal next choice is skipped. Because the choice is undone after its entire subtree is explored, every possible continuation is considered independently.

Algorithm plan

1. Initialize an empty path, a used array of length n, and an empty answers list.
2. If path has length n, append a copy to answers.
3. Otherwise, loop through all indices and skip those marked used.
4. Mark the chosen index, append its value, and call backtrack().
5. Pop the value and unmark the index before trying the next candidate.

Micro-example For [1,2,3], the root has children [1], [2], and [3]. The [1] subtree contains [1,2,3] and [1,3,2].

Pitfalls

• Forgetting used[i] = false after recursion corrupts sibling branches.
• Forgetting to pop from path leaves old values in later permutations.
• Use a copied path when recording a solution.

Recap

• Depth equals the next position to fill.
• The loop supplies all legal choices at that position.
• Undo is required for correctness, not merely optimization.

Learning goal: Trace all six answers for the concrete input [1,2,3].

Core idea The recursion explores the tree in depth-first order. It first commits to 1, fully explores every completion beginning with 1, then backs up and commits to 2, and finally to 3. The used[] state always describes only the current path.

Algorithm plan

• Begin at the root with path = [].
• Follow the first available candidate at each level.
• At depth three, record the completed arrangement.
• Backtrack one level and replace the most recent choice.
• Continue until the root has no unused choices.

Micro-example The first branch is [1] -> [1,2] -> [1,2,3], which records the first answer. Undoing 3 enables [1,3,2] without rebuilding the entire search from scratch.

Pitfalls

• A backtrack event must restore both path and used[].
• Sibling branches share a parent prefix but not a child choice.
• The final count should be 3! = 6.

Recap

• Depth-first search records [1,2,3], [1,3,2], then the two 2 branches and two 3 branches.
• Every leaf has length three.
• Clean restoration makes the six branches independent.

Learning goal: Diagnose the state-restoration bug and handle small inputs confidently.

Core idea Backtracking relies on a strict contract: a recursive call may change state temporarily, but it must return the state to its caller's version. If an element remains marked after its branch finishes, later siblings incorrectly believe that element is unavailable, so valid permutations disappear.

Algorithm plan

• Before recursion: mark the index and append the value.
• After recursion: pop the value and unmark the index.
• For n = 1, the single element is immediately a complete answer.
• Because values are distinct, no duplicate-skipping rule is needed.

Micro-example If [1] is left marked after exploring [1,2,3], the root cannot later choose 1 for branches beginning with 2 or 3. The result loses valid answers such as [2,1,3].

Pitfalls

• Empty path is not a solution unless the problem allowed n = 0; here n >= 1.
• Do not mutate the saved solution when later backtracking changes path.
• Swapping in place also requires swapping back after recursion.

Recap

• Restoration is part of the algorithm's correctness proof.
• The smallest input has exactly one permutation.
• Distinctness means each index can be tracked directly.

Learning goal: Analyze the cost of permutation backtracking and summarize the reusable pattern.

Core idea There are n! complete permutations. Constructing or copying each answer costs O(n), so the total time is O(n · n!). The recursion depth, path, and used[] each require linear auxiliary space; excluding the returned output, auxiliary space is O(n).

Algorithm plan

• Count the n! leaves in the decision tree.
• Account for O(n) work to copy each complete path.
• Account for O(n) recursion depth and state arrays.
• Treat the output storage separately because it necessarily contains all answers.

Micro-example For n = 3, there are 3! = 6 leaves. Copying three values at each leaf gives work proportional to 3 · 6 = 18, which matches the O(n · n!) bound.

Pitfalls

• Do not report only O(n!) when every answer must be copied.
• Output storage is O(n · n!), even though auxiliary working space is O(n).
• Backtracking does not avoid the factorial number of answers; it organizes their generation.

Recap

• Time: O(n · n!), including output construction.
• Auxiliary space: O(n), excluding returned permutations.
• The transferable pattern is choose, recurse, and undo.