Permutations

Return all permutations of the array.

Backtracking

Pattern fit

Unlike subsets, order matters, so each layer chooses one still-unused element and marks it as consumed for deeper recursion.

Key observation

Each recursion level fixes one position in the permutation.

Target complexity

O(n * n!) / O(n)

How to break down the solution cleanly

Unlike subsets, order matters, so each layer chooses one still-unused element and marks it as consumed for deeper recursion.

Each recursion level fixes one position in the permutation.

Model the decision tree explicitly.

Choose the next candidate set for the current depth.

Reference implementation

Python

# Generic pattern template
def backtrack(path):
    if complete(path):
        answer.append(path[:])
        return
    for choice in choices(path):
        if not valid(choice, path):
            continue
        path.append(choice)
        backtrack(path)
        path.pop()