LeetCode 46: Permutations

Problem Restatement

We are given an array nums containing distinct integers.

We need to return all possible permutations of the array. A permutation is one possible ordering of all elements.

The answer may be returned in any order. The official problem states: given an array nums of distinct integers, return all possible permutations.

Example:

nums = [1, 2, 3]

The possible permutations are:

[
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1],
]

Input and Output

Function shape:

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

First Thought: Build Every Ordering

A permutation is an ordering of all numbers.

For each position, we can choose any number that has not already been used.

For example, with:

nums = [1, 2, 3]

At the first position, we can choose 1, 2, or 3.

If we choose 1, then the next position can choose 2 or 3.

If we choose 2, then the next position can choose 1 or 3.

This forms a decision tree.

Backtracking is a natural fit because we build one partial permutation, explore it, then undo the last choice and try another choice.

Key Insight

Use a temporary list called path.

path stores the permutation currently being built.

Also use a boolean array called used.

used[i] tells us whether nums[i] is already inside path.

When path has the same length as nums, we have built one full permutation. Add a copy of path to the answer.

The copy matters because path will continue changing during backtracking.

Algorithm

Initialize:

ans = []
path = []
used = [False] * len(nums)

Define a recursive function backtrack().

Inside backtrack():

1. If len(path) == len(nums), append a copy of path to ans.
2. Otherwise, loop through each index i.
3. If used[i] is true, skip it.
4. Choose nums[i].
5. Mark it as used.
6. Recurse.
7. Undo the choice by popping from path and marking it unused.

Return ans.

Walkthrough

Use:

nums = [1, 2, 3]

Start:

path = []
used = [False, False, False]

Choose 1:

path = [1]
used = [True, False, False]

Choose 2:

path = [1, 2]
used = [True, True, False]

Choose 3:

path = [1, 2, 3]
used = [True, True, True]

Now the path length is 3, so we append:

[1, 2, 3]

Then backtrack.

Remove 3, then try the next available choice after 2. There is no next choice, so remove 2.

Now from:

path = [1]
used = [True, False, False]

choose 3, then choose 2.

This gives:

[1, 3, 2]

The recursion continues until every first choice has been explored.

Final result:

[
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1],
]

Correctness

The algorithm builds permutations one position at a time.

At each recursive call, path contains distinct elements from nums, because a number can be added only when its corresponding used[i] value is false.

When len(path) == len(nums), the path contains exactly n distinct elements chosen from an array of length n. Therefore, it contains every element exactly once, so it is a valid permutation.

The loop tries every unused number at each position. Therefore, for any valid permutation, the algorithm can follow the exact sequence of choices that creates it.

Backtracking restores the state after each choice, so choices from one branch do not block choices in another branch.

Thus, the algorithm generates every valid permutation, and because each position uses an unused number, it never generates an invalid permutation.

Complexity

The output itself contains n! permutations, each of length n, so the returned answer uses O(n * n!) space.

Implementation

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

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

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

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

                backtrack()

                path.pop()
                used[i] = False

        backtrack()
        return ans

Code Explanation

We store all finished permutations in:

ans = []

The current partial permutation is:

path = []

The used array prevents using the same element twice:

used = [False] * len(nums)

The base case is:

if len(path) == len(nums):

At this point, path is a complete permutation.

We append a copy:

ans.append(path[:])

Then we try each number:

for i in range(len(nums)):

If it is already used, skip it:

if used[i]:
    continue

Otherwise, choose it:

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

Then recurse.

After recursion returns, undo the choice:

path.pop()
used[i] = False

This reset is what allows the next branch to start from a clean state.

Testing

def normalize(result):
    return sorted(tuple(x) for x in result)

def run_tests():
    s = Solution()

    assert normalize(s.permute([1, 2, 3])) == normalize([
        [1, 2, 3],
        [1, 3, 2],
        [2, 1, 3],
        [2, 3, 1],
        [3, 1, 2],
        [3, 2, 1],
    ])

    assert normalize(s.permute([0, 1])) == normalize([
        [0, 1],
        [1, 0],
    ])

    assert normalize(s.permute([1])) == normalize([
        [1],
    ])

    assert normalize(s.permute([-1, 2])) == normalize([
        [-1, 2],
        [2, -1],
    ])

    print("all tests passed")

run_tests()