MediumBlind75ArrayBacktracking

Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Examples

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

All 6 permutations of [1,2,3].

Input
nums = [0,1]
Output
[[0,1],[1,0]]

Both permutations of [0,1].

Constraints

  • •1 <= nums.length <= 6
  • •-10 <= nums[i] <= 10
  • •All the integers of nums are unique.

Approaches

Use swapping to generate permutations in-place.

CodeT: O(n * n!) | S: O(n)
def permute(nums):
    result = []
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack(0)
    return result

Track which elements are used in the current permutation.

CodeT: O(n * n!) | S: O(n)
def permute(nums):
    result = []
    def backtrack(current, used):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                current.append(nums[i])
                backtrack(current, used)
                current.pop()
                used[i] = False
    backtrack([], [False] * len(nums))
    return result

Insert each number at every position in all existing permutations.

Diagram

nums = [1,2,3] Start: [[]] Add 1: [[1]] Add 2: [[2,1],[1,2]] Add 3: [[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]]
CodeT: O(n^2 * n!) | S: O(n * n!)
def permute(nums):
    result = [[]]
    for num in nums:
        new_result = []
        for perm in result:
            for i in range(len(perm) + 1):
                new_result.append(perm[:i] + [num] + perm[i:])
        result = new_result
    return result

Complexity Comparison

Backtracking - Swap
T: O(n * n!)S: O(n)

Use swapping to generate permutations in-place.

Backtracking - Used Array
T: O(n * n!)S: O(n)

Track which elements are used in the current permutation.

Insertion Method
T: O(n^2 * n!)S: O(n * n!)

Insert each number at every position in all existing permutations.

Common Mistakes

Not restoring state after backtracking

Using the wrong loop range

Forgetting to handle the base case correctly

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems