Permutations: Complete Backtracking Guide

Given an array of distinct integers, return all possible permutations. You can return the answer in any order.

This is LeetCode 46: Permutations, and it is one of the most important backtracking problems to know cold. If Subsets is the "hello world" of backtracking, Permutations is the next step up. Instead of choosing whether to include or skip each element, you are choosing where to place each element. Every element must appear exactly once, and the order matters.

Why this problem matters

Permutations teaches you how the choose-explore-unchoose template adapts when you need to use every element rather than selecting a subset. In Subsets, the branching decision is "include or skip." In Permutations, the branching decision is "which unused element goes in this position?" That small shift changes the recursion tree from 2^n leaves to n! leaves.

This matters because a huge number of interview problems are just permutations with constraints bolted on. Generating parentheses, letter combinations, solving Sudoku, and N-Queens all use the same recursive skeleton. The only differences are the branching rules and the pruning conditions. If you can generate all permutations from scratch, you have the foundation for all of them.

Backtracking permutations also gives you a solid intuition for n! complexity. When someone asks "why is this O(n!)?" you can picture the recursion tree: n choices at level 0, n-1 at level 1, n-2 at level 2, and so on. That is n! leaf nodes.

The key insight

Think of building a permutation as filling positions left to right. For position 0, you have n choices. For position 1, you have n-1 remaining choices. For position 2, n-2, and so on until every position is filled.

The swap technique makes this concrete. Instead of maintaining a separate "used" set, you swap elements in the array itself:

1. At depth start, swap nums[start] with each element from index start to n-1. Each swap puts a different element into position start.
2. Recurse with start + 1 to fill the remaining positions.
3. After the recursive call returns, swap back (unchoose) to restore the array for the next iteration.
4. When start == n, every position is filled. Record the current arrangement.

The elements before index start are "fixed" (already placed). The elements from index start onward are "available" (candidates for the current position). Each swap picks one candidate, and the un-swap puts it back.

The backtracking solution (swap approach)

def permute(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return

        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # choose
            backtrack(start + 1)                           # explore
            nums[start], nums[i] = nums[i], nums[start]  # unchoose

    backtrack(0)
    return result

Let's walk through this.

The outer function initializes result and calls backtrack(0). The argument start represents the position we are currently filling.

Inside backtrack, the base case is start == len(nums). When we have fixed all positions, we have a complete permutation. We copy it with nums[:] and add it to the result.

The for loop is where the magic happens. We iterate i from start to the end of the array. For each i, we swap nums[start] with nums[i]. This effectively says "put element nums[i] into position start." After the swap, we recurse with start + 1 to fill the next position.

The unchoose step swaps back. This is critical. Without it, the array stays scrambled and subsequent iterations produce wrong results. The swap-back restores the array to its state before this iteration, so the next value of i can try a different element in position start.

Visual walkthrough

Let's trace through the algorithm with nums = [1, 2, 3]. Watch how each level of recursion fixes one more position, and how swapping back opens up the next branch.

The tree has 3! = 6 leaves. At level 0, we have 3 choices (swap position 0 with index 0, 1, or 2). At level 1, we have 2 remaining choices. At level 2, only one element is left, so we record the permutation. The backtracking is visible in steps 4 and 5: after recording [1,2,3] and [1,3,2], we un-swap to restore position 0 and then try putting 2 in front.

Alternative: the used-set approach

If in-place swapping feels tricky, there is an alternative that uses a boolean array (or set) to track which elements have been used:

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True              # choose
            current.append(nums[i])
            backtrack(current)           # explore
            current.pop()               # unchoose
            used[i] = False

    backtrack([])
    return result

This version builds the permutation in a separate list current and uses used[i] to prevent reusing the same element. The choose step marks the element as used and appends it. The unchoose step pops it and marks it as unused.

Both approaches produce the same result with the same time complexity. The swap version uses O(1) extra space (it reuses the input array), while the used-set version needs O(n) for the used array plus O(n) for current. In interviews, the swap version is slightly more impressive, but either one is perfectly fine. Use whichever you can write correctly under pressure.

Complexity analysis

Time is O(n * n!). There are n! permutations, and copying each one into the result takes O(n). The recursion tree has n! leaves and roughly e * n! total nodes (the sum n!/0! + n!/1! + ... + n!/n! converges to e * n!), with O(1) work at each node (excluding the copy). The dominant cost is the n! copies of length n.

Space is O(n * n!) for storing all permutations in the result. The recursion stack uses O(n) additional space (one frame per level). If you ignore the output, the extra space is O(n) for the swap version and O(n) for the used-set version.

Edge cases

Before submitting, check these:

• Single element: nums = [1]. Should return [[1]]. Only one permutation exists.
• Two elements: nums = [1, 2]. Should return [[1, 2], [2, 1]]. Good sanity check for the swap logic.
• Already sorted vs unsorted input: The order of nums does not affect correctness, but it changes which permutation you generate first.
• Large n: With n = 8, there are 40,320 permutations. The algorithm handles it, but n = 10 gives 3.6 million. Be aware of the factorial growth.

The building blocks

This problem is built on one core reusable piece that CodeBricks drills independently.

Choose-explore-unchoose (backtracking template)

The same skeleton that powers Subsets, Word Search, and every other backtracking problem:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)      # choose
        backtrack(state)          # explore
        undo_choice(choice)       # unchoose

In the swap-based Permutations solution, make_choice is swapping nums[start] with nums[i]. backtrack recurses with start + 1. undo_choice is swapping them back. The difference from Subsets is the candidate set: instead of iterating from start and choosing to include/skip, you iterate from start and swap each remaining element into the current position.

This same template handles:

• Permutations II (with duplicates): sort the input, then skip duplicate swaps at each level.
• Subsets: iterate from start, include/skip instead of swap.
• Combination Sum: allow reuse by recursing with i instead of i + 1.
• N-Queens: the choice is which column to place the queen in each row.

The key insight is that Subsets decides "should this element be in the result?", while Permutations decides "which element goes in this position?" Both use the exact same choose-explore-unchoose skeleton. The only thing that changes is the loop and what constitutes a choice.

Common mistakes

1. Forgetting to copy before recording. Just like in Subsets, if you write result.append(nums) instead of result.append(nums[:]), every entry in the result will be a reference to the same list. After all the swaps and un-swaps, they will all end up as the original array. Always copy.

2. Not swapping back (un-choosing). The most critical bug. If you skip the second swap, the array stays modified. Every subsequent loop iteration operates on wrong data. Your output will have duplicates and missing permutations.

3. Using range(0, len(nums)) instead of range(start, len(nums)). Starting from 0 every time means you place already-fixed elements back into later positions. This produces duplicates and incorrect results. The loop must start at start so you only consider unfixed elements.

4. Confusing the swap approach with the used-set approach. If you mix the two (swapping in place but also using a used array), you get confused state. Pick one and stick with it.

When to use this pattern

Look for these signals:

• The problem asks for all permutations or all arrangements
• Every element must appear exactly once in each result
• Order matters (unlike subsets where [1,2] and [2,1] are the same)
• Constraints mention n is 8 or less or similar small bounds (hinting at n! enumeration)

Problems that use the same backtracking permutations pattern:

• Permutations II (LeetCode 47): same structure with duplicate handling
• Next Permutation (LeetCode 31): not backtracking, but understanding all permutations helps you see the lexicographic ordering
• Letter Combinations of a Phone Number (LeetCode 17): build all arrangements from digit-to-letter mapping
• N-Queens (LeetCode 51): place one queen per row, which is essentially permuting column positions

From understanding to recall

You understand the recursion tree. You see how each level fixes one position and how swapping back opens up the next branch. But can you write the swap-based backtracking solution from scratch in under two minutes?

That is what interviews demand. The backtracking permutations LeetCode problem looks simple on paper, but under pressure, small details trip people up: swapping with the wrong index, forgetting to swap back, copying the result incorrectly. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the choose-explore-unchoose template and the permutation-specific swap loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "generate all permutations" and the code flows out without hesitation.

The choose-explore-unchoose pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subsets - The simplest backtracking problem using the same choose-explore-unchoose template. Compare it to Permutations to see how "include/skip" differs from "which element goes here?"
• Word Search - Grid backtracking using the same template. Shows how choose-explore-unchoose adapts to a 2D grid context instead of a 1D array.
• Course Schedule - Graph traversal that also explores all paths. Different pattern (topological sort), but the recursive structure has a similar feel.

CodeBricks breaks Permutations into its choose-explore-unchoose building block, then drills it independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.