Permutations (LeetCode 46)

The problem

You get a list of distinct integers. Return every possible ordering (permutation) of them. Any order of the output list is fine.

Input:  nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Three choices for the first slot, two for the second, one for the last: 3! = 6.

How to think about it

Start with brute force. You could generate every length-n sequence over the elements (nⁿ of them) and keep only the ones with no repeats. For n = 6 that’s 46,656 sequences to find 720 permutations. Most of the work is thrown away.

The key insight: build the permutation slot by slot, and never pick an element twice. For the first slot you may pick any element. For the second, any element except the one already placed. So at each step the choices are “every element not used yet”. Track that with a boolean used array, one flag per index.

Why not a start index like Subsets? In Subsets, [1,2] and [2,1] are the same answer, so a start index forbids going backwards. In permutations they are different answers. Order matters, so every unused element is a valid next choice, including ones to the left. That’s the one-line difference between the two templates, and interviewers like to ask about it.

Record only full paths. A permutation is complete when len(path) == len(nums). Partial paths are not answers, so you record at the leaves, not at every node.

Which pattern is this? Backtracking: choose, recurse, undo. The tell is “all orderings / all arrangements”. Undoing means popping from path and clearing the used flag.

Approach

1. Keep path, res, and used = [False] * n.
2. In bt(path, used): if path has n elements, record a copy and return.
3. Otherwise, for every index i that isn’t used: mark it used, append nums[i], recurse, then pop and unmark.
4. Call bt([], [False] * n).

Solution

def permutations(nums):
    res = []
    def bt(path, used):
        if len(path) == len(nums): res.append(path[:]); return   # full ordering
        for i in range(len(nums)):
            if used[i]: continue                                  # already in this path
            used[i] = True; path.append(nums[i]); bt(path, used); path.pop(); used[i] = False
    bt([], [False] * len(nums)); return res
# permutations([1,2,3]) -> 6 permutations

Dry run

On nums = [1, 2, 3], the leaves in the order they’re reached:

Note the second pick of the third row is 1, an element to the left of 2. A start index would have blocked it.

Complexity

• Time: O(n·n!). There are n! leaves, and copying each one costs O(n). The internal nodes add less than that.
• Space: O(n) extra. Recursion depth, path and used are all n long. The output is O(n·n!).

Edge cases and pitfalls

• Single element returns [[x]]. Empty input returns [[]] with this code (one empty ordering).
• Forgetting used[i] = False on the way back. Later branches think the element is still taken, and you get far fewer than n! results.
• Appending path instead of path[:]. All entries share one list, which ends up empty.
• Duplicates in the input produce repeated permutations. That’s Permutations II.
• An alternative is swapping elements in place (swap i into position start, recurse, swap back). It avoids the used array but changes the output order.

Related problems

• Permutations II (LeetCode 47): the same template with duplicate values in the input.
• Subsets (LeetCode 78): order doesn’t matter, so a start index replaces used.
• N-Queens (LeetCode 51 / 52): each row picks an unused column, a permutation with extra pruning.