Medium

Permutations

082

Return all permutations of nums sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3
  ]
}

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

FUNCTION SHAPE

nums: intArray→intMatrix

SOLUTION NOTE

Why does this work?

[1,2,3] -> [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

We first have j = i, so the swap does nothing and the first value is still 1. Then recursively, we want all permutations of the rest of the array [2,3].

So all permutations of [1,2,3] that start with 1 = [1] + permutations of [2,3].

permutations of [2,3] = [2,3], [3,2]

all permutations of [1,2,3] that start with 1 = [1] + ([2,3], [3,2]) = [1,2,3], [1,3,2].

Now, the recursion has finished, so we try moving 2 to the first value, and now 1 is in the second index. Then recursively, we want all permutations of the rest of the array [1,3].

So all permutations of [1,2,3] that start with 2 = [2] + permutations of [1,3].
… you get the idea.

N choices for index 0, n-1 choices for index 1, … 1 choice for index n-1.

Reveal reference solution +

pythonREFERENCE

def permute(self, nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res = []

    # swap
    def backtrack(i):
        if i == n:
            res.append(nums.copy())
        else:
            for j in range(i, n):
                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i+1)  # has to be i+1, NOT j+1 !!!
                nums[i], nums[j] = nums[j], nums[i]

    backtrack(0)
    return res

TimeO(n*n!)

SpaceO(n*n!)

Open on LeetCode ↗