LeetCode 46 – Permutations

Permutations is the reference implementation of backtracking, and its value is the contrast with the combination problems. Combination Sum passes a start index down the recursion to stop the same set appearing in different orders. Here the different orders are the answer, so start disappears — and something else has to take its job.

The problem

Given an array of distinct integers, return every possible ordering.

[1,2,3] -> [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
[0,1]   -> [[0,1], [1,0]]
[1]     -> [[1]]

n distinct values produce exactly n! permutations — 6 for three elements, 3,628,800 for ten. The output is the bottleneck, and no algorithm can beat it.

What replaces the start index

In a combination problem, position does not matter, so the recursion is only ever allowed to look forward from where it arrived. That single rule forces every result into one canonical order and makes duplicates structurally impossible.

A permutation is the opposite: [1,2,3] and [3,2,1] are different answers, so every level must consider every position — including ones to the left. The loop therefore always starts at 0.

But an element still must not be used twice within one permutation, and with the forward-only rule gone, nothing enforces that. So you track it explicitly with a used[] array:

Being able to draw that table is worth more than either solution alone — it shows the two are one template with a parameter.

Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> path,
                           int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));   // copy: path keeps mutating
            return;
        }

        for (int i = 0; i < nums.length; i++) {   // 0, not start: order matters here
            if (used[i]) continue;

            used[i] = true;
            path.add(nums[i]);

            backtrack(result, path, nums, used);

            path.remove(path.size() - 1);         // undo, both of them
            used[i] = false;
        }
    }
}

Undo both. Two pieces of state changed on the way down, so two must be restored on the way back up. Forgetting used[i] = false is the classic bug here, and it fails quietly in a specific way: the first branch consumes elements and never releases them, so you get one permutation and then nothing. Output that is too short rather than an exception.

used[] rather than path.contains(nums[i]). contains is a linear scan on every check, adding a factor of n — and it breaks outright the moment values repeat, which is exactly what Permutations II asks for. The array is O(1) per lookup and generalises.

Python

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        path = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                result.append(path[:])       # copy
                return

            for i in range(len(nums)):
                if used[i]:
                    continue

                used[i] = True
                path.append(nums[i])

                backtrack()

                path.pop()                   # undo, both of them
                used[i] = False

        backtrack()
        return result

itertools.permutations(nums) is the real-world answer and returns tuples. Name it, then write the loop.

Complexity

O(n · n!) time: n! permutations, each costing O(n) to copy into the result. The recursion tree has more nodes than that, but the work at the internal nodes is dominated by the leaves.

Space is O(n) — the path, the used array and the recursion depth are all linear — not counting the output, which is O(n · n!) and unavoidable.

The honest framing: "the output is factorial, so nothing can be polynomial; this does O(1) work per node of a tree whose leaves are exactly the answers." That is the sentence to say, not a recited formula.

The swap-based variant

There is a neat alternative that needs no used[] and no separate path: swap each remaining element into the current position, recurse, swap back.

private void permute(int[] nums, int k, List<List<Integer>> result) {
    if (k == nums.length) {
        List<Integer> copy = new ArrayList<>();
        for (int v : nums) copy.add(v);
        result.add(copy);
        return;
    }

    for (int i = k; i < nums.length; i++) {
        swap(nums, k, i);
        permute(nums, k + 1, result);
        swap(nums, k, i);      // undo
    }
}

Less bookkeeping, and it mutates the caller's array. Its real drawback is that the de-duplication trick for Permutations II does not transfer — swapping destroys the sorted order the skip rule depends on. Learn the used[] version as the default.

What the interviewer is checking

• That the loop starts at 0, and that you can say why a start index would be wrong here.
• That both pieces of state are undone after recursing.
• That the path is copied into the result, not stored by reference.
• That you use used[] rather than scanning the path.
• That you recognise the output size bounds any possible solution.
• A single element, and an empty array (which yields one empty permutation).