46. Permutations

Reformulated question¶

Return every ordering of a list of distinct integers.

Example:

in:  nums = [1, 2, 3]
out: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
note: same values, different orders; any output order is valid

Key trick¶

Use backtracking:

Choose one unused number.
Add it to the current permutation.
Recurse.
Undo the choice.

A clean interview version swaps in-place so you avoid extra sets and repeated differences.

Trap¶

Common mistakes:

Appending path directly instead of a copy, which makes all answers mutate together.
Forgetting to undo the choice after recursion.
Recomputing unused elements with set difference on every call, adding unnecessary overhead.
Assuming output order matters.

Why this question is interesting¶

It is the classic backtracking template:

build partial answer
recurse
undo

It also tests whether you can reason about generating all \(n!\) results, so exponential output is expected.

Solution with idiomatic Python¶

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []

        def backtrack(first: int) -> None:
            # If we fixed every position, we built one full permutation.
            if first == len(nums):
                result.append(nums[:])  # copy current arrangement
                return

            # Put each remaining number into position `first`.
            for i in range(first, len(nums)):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]  # undo

        backtrack(0)
        return result

Complexity:

Time: \(O(n \cdot n!)\)
Space: \(O(n)\) auxiliary, excluding output

Library alternative:

from itertools import permutations


class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        return [list(p) for p in permutations(nums)]

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1], [[1]]),
        ([0, 1], [[0, 1], [1, 0]]),
        (
            [1, 2, 3],
            [
                [1, 2, 3],
                [1, 3, 2],
                [2, 1, 3],
                [2, 3, 1],
                [3, 1, 2],
                [3, 2, 1],
            ],
        ),
        ([-1, 0, 1], [[-1, 0, 1], [-1, 1, 0], [0, -1, 1], [0, 1, -1], [1, -1, 0], [1, 0, -1]]),
    ],
)
def test_permute(nums, expected):
    got = Solution().permute(nums)
    assert sorted(got) == sorted(expected)

Comment on your solution¶

Your solution is close and the backtracking idea is correct.

Issues:

result.append(path) is a bug.
- You must append a copy:

result.append(path[:])

nums_set.difference(used) on every recursion is unnecessary extra work.
Tracking used as values works here only because values are distinct.
In-place swapping is simpler and more standard for this question.

## Solution
# WRONG
# I should use path.copy() when appending to result
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        nums_set = set(nums)
        result = []
        path = []

        def dfs(used):
            if len(used) == len(nums):
                result.append(path)
                return
            complement = nums_set.difference(used)
            for x in complement:
                path.append(x)
                used.add(x)
                dfs(used)
                used.remove(x)
                path.pop()

        dfs(set())
        return result


Solution().permute([1,2])

Your fixed version would be:

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        nums_set = set(nums)
        result = []
        path = []

        def dfs(used):
            if len(used) == len(nums):
                result.append(path[:])
                return

            for x in nums_set.difference(used):
                path.append(x)
                used.add(x)
                dfs(used)
                used.remove(x)
                path.pop()

        dfs(set())
        return result