LeetCode #46 Medium

Permutations

Given an array nums of distinct integers, return all possible permutations (orderings). For [1,2,3] there are 3! = 6.

backtrackingrecursionarray

Open on LeetCode ↗

02

Intuition

Build each ordering slot by slot. For every position, try each number that hasn't been used yet, recurse to fill the next slot, then undo the choice and try the next number.

How to spot this pattern

When order matters and every element must appear, you're permuting, not combining — so each level of the recursion scans the whole array rather than starting from an index. That's the structural difference from combination-sum: combinations use a start cursor to enforce order, permutations use a used array because there is no order to enforce.

03

Approach

1

Each permutation fixes a number per slot

A permutation is an arrangement that uses every element exactly once. So think of it as filling slots left to right: for slot 0 choose any number, for slot 1 any of the remaining, and so on. The branching factor shrinks by one each level until a full ordering is complete.

2

Track which numbers are used

Carry a used flag set (or boolean list). At each level, loop over all numbers and skip the ones already on the path. Pick an unused number, mark it used, append it, and recurse. This guarantees no value repeats within a single permutation.

3

Record at the leaf, then backtrack

When the path length equals the input length, every slot is filled — record a copy of the path. After each recursive call, pop the number and clear its used flag so the next iteration can try it elsewhere. That choose → explore → un-choose loop is the heart of backtracking. There are n! leaves.

04

Solution & live demo

▶1class Solution:
▶2    def permute(self, nums):
▶3        res = []
▶4        used = [False] * len(nums)
▶5        def backtrack(path):
▶6            if len(path) == len(nums):
▶7                res.append(path[:])
▶8                return
▶9            for i in range(len(nums)):
▶10                if used[i]:
▶11                    continue
▶12                used[i] = True
▶13                path.append(nums[i])
▶14                backtrack(path)
▶15                path.pop()
▶16                used[i] = False
▶17        backtrack([])
▶18        return res

05

Common pitfalls

Using a `start` index like a combination problem

✗ Wrong

def backtrack(start, path):
    for i in range(start, len(nums)):
        ...

✓ Right

def backtrack(path):
    for i in range(len(nums)):
        if used[i]: continue
        ...

A start cursor only ever moves forward, so [2, 1] can never be built after [1, 2] — you'd generate combinations and return a single permutation. Permutations must be free to reach back to earlier elements, which is why membership is tracked by a flag rather than a position.

Clearing `used[i]` but not popping the path

✗ Wrong

path.append(nums[i])
backtrack(path)
used[i] = False

✓ Right

path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False

The two pieces of state must unwind together. Releasing the element for reuse while leaving it in path lets it appear twice in the same permutation and pushes path past len(nums). Undo every mutation you made, in reverse order.

06

Edge cases

Single element

One permutation, the list itself.

Empty input

Returns [[]] — one permutation, the empty ordering.

Distinct values assumed

With duplicates you'd get repeated permutations; Permutations II adds a sort-and-skip to dedupe.

07

Complexity

Time

O(n·n!)

Space

O(n)

n! permutations, each O(n) to build and copy; recursion depth is n.