Permutations

+10

You get a list nums of different integers. Return every ordering of those values, each a list that uses every value exactly once, so n values give n! orderings. List them in lexicographic order: compare two orderings position by position and let the first difference decide. For [1, 2, 3] that puts [1, 2, 3] first and [3, 2, 1] last.

Function

permute(nums: integer-array) → integer-2d-array

numsinteger-array: the values, all different, in any order
Returnsinteger-2d-array: every ordering of the values, listed in lexicographic order

Constraints

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
All values in nums are different.
nums may come in any order.

Examples

Input: nums = [3, 1, 2]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: Three values have 3! = 6 orderings. Sorted, the values are 1, 2, 3, so the orderings that start with 1 come first, and [1, 2, 3] comes before [1, 3, 2] because 2 is smaller than 3 at the second position. The order of the input does not matter.

Input: nums = [2, -1]
Output: [[-1, 2], [2, -1]]
Explanation: Two values can be written in two orders. [-1, 2] comes first because -1 is smaller than 2.

+13 hidden tests on Submit

Follow-up

Given one ordering, can you produce the next one in lexicographic order in place, in O(n) time and O(1) extra space?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A list of n different values has n! orderings, 720 for six values, and the answer has to list them all, so the work is at least n × n!. The challenge is to build each ordering once and to emit them in lexicographic order. Backtracking over the sorted values, always trying the smallest unused value first, does both at the same time.

Insert into every gap, then sort

Intuition

Grow the orderings one value at a time. With no values there is one ordering, the empty list. To add the value 3 to the ordering [1, 2], put it into each of its three gaps: [3, 1, 2], [1, 3, 2] and [1, 2, 3]. Do that for every ordering you have, and the orderings of k values turn into the orderings of k+1 values.

Every ordering of k+1 values is built exactly once: take the newest value out of it and you get the one ordering it grew from, while the newest value's position names the gap. So the counts go 1, 2, 6, 24, and n values give n! orderings.

They do not come out in the required order. For [1, 2, 3] the first ordering built is [3, 2, 1], so you finish with a sort that compares position by position. That sort is the expensive part: n! orderings need about n! × log(n!) comparisons, and each reads up to n values. For six values that is roughly 720 × 9.5 × 6, about 41,000 reads. The method also holds a whole generation of orderings in memory while it builds the next one.

Algorithm

Start with a list that holds one empty ordering.
For each value in nums, build a new list: for every ordering so far and every gap from 0 to its length, copy the ordering with the value inserted at that gap.
Replace the old list with the new one.
Sort the orderings position by position and return them.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Backtracking with a used array

Intuition

Fill n slots from left to right. The first slot has n candidates, the second n-1, and so on, which is where n! comes from. Draw those choices as a tree: the root is an empty path, each edge places one more value, and each leaf, at depth n, is one finished ordering. For sorted values 1, 2, 3 the root has the children [1], [2] and [3]; [1] has the children [1, 2] and [1, 3]; each of those has one leaf.

Backtracking walks this tree with one shared path and a used flag per value. At each node it loops over the values and skips the used ones. For each free value it chooses (marks it used and appends it), explores (recurses one level deeper), then un-chooses (removes it and marks it free). The un-choose step restores the exact state the loop had before, so the next value is tried from the same node. A path of length n is a leaf: record a copy and return.

The order comes out right on its own. The loop tries the smallest free value first, and the walk finishes every ordering that starts with a given prefix before it changes that prefix. So all orderings that start with 1 come before any that start with 2, and among them [1, 2, ...] comes before [1, 3, ...]. That is lexicographic order. It is also why you sort nums first: the loop goes by index, so the indexes must be in value order.

The tree has about e × n! nodes (e is about 2.72), and each runs a loop of n, so the time is O(n × n!), the same order as the size of the answer. Besides the output, the path, the flags and the call stack each hold at most n entries.

Algorithm

Sort the values and make a used array of n false flags.
Write explore(). If path holds n values, append a copy to the result and return.
Otherwise, for each index i from 0 to n-1 whose value is free: mark it used and append values[i] (choose), call explore() (explore), then remove it and mark it free (un-choose).
Call explore() once and return the result.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Pitfalls and edge cases

Backtracking bugs are almost always state that is not restored, or state that is shared by accident.

Recording path instead of a copy of it. All n! entries end up as the same list, which is empty once the walk is over.
Undoing only half of a choice. If you remove the value but leave used[i] set, that value never appears again in a later branch and you return fewer than n! orderings.
Not sorting nums first. The walk still finds every ordering, but they follow the order of the input, so the input [3, 1, 2] would be listed first.
Using the swap method (swap nums[start] with each later position, recurse, swap back) without a final sort. It finds all n! orderings, but for [1, 2, 3] it lists [3, 2, 1] before [3, 1, 2].
Checking for a used value with a search through path. It works here only because the values are different, and it costs n at every step. A flag per index is O(1) and still works when values repeat.

Frequently asked questions4

How many permutations does a list of n distinct elements have?

n!, read n factorial: n choices for the first position, n-1 for the second, down to one for the last, multiplied together. Three values give 6 orderings, six give 720, and ten already give 3,628,800, which is why permutation problems keep n small.

What is the time complexity of generating all permutations?

O(n × n!). There are n! orderings and writing each one out takes n steps, so no method can do better when it has to return them all. Backtracking reaches this bound, and besides the output it needs O(n) space for the current path, the used flags and the recursion.

Why does backtracking produce permutations in lexicographic order?

It is a depth-first walk that tries the smallest available value first. It finishes every ordering that starts with a given prefix before it moves to the next prefix, and it tries prefixes from small to large. That matches the way a dictionary orders words, as long as the input is sorted before the walk starts.

How do you generate permutations when the input has duplicates?

Sort the values and, at each position, skip a value that equals the value before it while that earlier copy is not in use: i > 0, values[i] == values[i-1] and !used[i-1]. That forces equal values to be placed in their original order, so each distinct ordering is built once.

Python

def permute(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [3, 1, 2]

Expected

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]