Permutations

Problem

Given an array of distinct integers, return all possible permutations in any order.

Approach

Backtracking with a visited set. At each position, try every unused element, mark it used, recurse, then unmark.

When to Use

All orderings — "generate all permutations", "all arrangements", brute-force over orderings for small n. Building block for next-permutation and ranking/unranking algorithms.

Complexity

Time	O(n * n!)
Space	O(n) (recursion depth + visited set)

Implementation

SolutionTestsChallenge

permutations

Permutations — generate all permutations of a list.

Problem

Given an array of distinct integers, return all possible permutations in any order.

Approach

Backtracking with a visited set. At each position, try every unused element, mark it used, recurse, then unmark.

When to use

All orderings — "generate all permutations", "all arrangements", brute-force over orderings for small n. Building block for next-permutation and ranking/unranking algorithms.

Complexity

Time: O(n * n!) Space: O(n) (recursion depth + visited set)

permutations

permutations(nums: Sequence[int]) -> list[list[int]]

Return all permutations of nums.

sorted(permutations([1, 2, 3])) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Source code in src/algo/backtracking/permutations.py

def permutations(nums: Sequence[int]) -> list[list[int]]:
    """Return all permutations of *nums*.

    >>> sorted(permutations([1, 2, 3]))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """
    result: list[list[int]] = []
    used = [False] * len(nums)

    def backtrack(path: list[int]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result

tests/backtracking/test_permutations.py

"""Tests for permutations generation."""

import math

from hypothesis import given
from hypothesis import strategies as st

from algo.backtracking.permutations import permutations


class TestPermutations:
    def test_three_elements(self) -> None:
        result = permutations([1, 2, 3])
        assert len(result) == 6
        assert [1, 2, 3] in result
        assert [3, 2, 1] in result

    def test_single_element(self) -> None:
        assert permutations([1]) == [[1]]

    def test_two_elements(self) -> None:
        result = permutations([1, 2])
        assert sorted(result) == [[1, 2], [2, 1]]

    def test_empty(self) -> None:
        assert permutations([]) == [[]]

    def test_no_duplicates(self) -> None:
        result = permutations([1, 2, 3])
        tuples = [tuple(p) for p in result]
        assert len(tuples) == len(set(tuples))

    @given(
        data=st.lists(
            st.integers(min_value=-10, max_value=10),
            min_size=1,
            max_size=6,
            unique=True,
        ),
    )
    def test_factorial_count(self, data: list[int]) -> None:
        assert len(permutations(data)) == math.factorial(len(data))

Implement it yourself

Run: just challenge backtracking permutations

Then implement the functions to make all tests pass. Use just study backtracking for watch mode.

Reveal Solution

permutations

Permutations — generate all permutations of a list.

Problem

Given an array of distinct integers, return all possible permutations in any order.

Approach

Backtracking with a visited set. At each position, try every unused element, mark it used, recurse, then unmark.

When to use

All orderings — "generate all permutations", "all arrangements", brute-force over orderings for small n. Building block for next-permutation and ranking/unranking algorithms.

Complexity

Time: O(n * n!) Space: O(n) (recursion depth + visited set)

permutations

permutations(nums: Sequence[int]) -> list[list[int]]

Return all permutations of nums.

sorted(permutations([1, 2, 3])) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Source code in src/algo/backtracking/permutations.py

def permutations(nums: Sequence[int]) -> list[list[int]]:
    """Return all permutations of *nums*.

    >>> sorted(permutations([1, 2, 3]))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """
    result: list[list[int]] = []
    used = [False] * len(nums)

    def backtrack(path: list[int]) -> None:
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result