46_ Permutations

[Medium][Backtracking]

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]

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

Solution: Backtracking

Idea:

• Think this problems as a tree problem, put one integer in each layer and do a depth-first-search to get all the paths.

• When we generate the tree, we do depth first.

• Change the positions of integers so that we can create each permutation in place.

Time Complexity: $O(n \times n!)$ because there are $O(n!)$ permutations/paths, and on each node we have constant computation, thus for each path, there are $O(n)$ computations.

Space Complexity: $O(1)$

def permute(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    def helper(n):
        if n == len(nums) - 1:
            output.append(list(nums))
            return
        for i in range(n, len(nums)):
            nums[n], nums[i] = nums[i], nums[n]
            helper(n + 1)
            nums[n], nums[i] = nums[i], nums[n]

    output = []
    helper(0)
    return output