Permutations

Given a list of distinct integers, return all possible permutations: every ordering of the elements. For a list of length n there are n factorial permutations, and each must appear exactly once.

Example#

For nums = [1, 2, 3] the answer is the 6 orderings: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1]. For nums = [0, 1] the answer is [0, 1] and [1, 0].

Brute force note#

Inserting each element into every position of partial results also works, but the backtracking formulation is the standard interview answer and extends cleanly to constrained variants.

Optimal approach#

Backtrack while tracking which elements are already used. At each level, try every unused element as the next choice, mark it used, recurse to fill the rest of the ordering, then unmark it (the undo step) so sibling branches can use it. When the current path reaches full length, record it as one complete permutation.

 1def permute(nums):
 2    result = []
 3    used = [False] * len(nums)
 4
 5    def backtrack(path):
 6        if len(path) == len(nums):
 7            result.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
18    backtrack([])
19    return result
20
21
22print(permute([1, 2, 3]))
23# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
24print(permute([0, 1]))  # [[0, 1], [1, 0]]

Complexity#

Time is O(n times n factorial): there are n factorial permutations and copying each costs O(n). Space is O(n) for the recursion depth, used array, and current path, excluding the output.

This is the canonical permutation backtracking drill. Master the used-marker technique there, then continue through the 60-day curriculum.