MediumLeetCode #46Backtracking

Permutations

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

Constraints

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

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]]

Solution Approach

Recursively explore all possible solutions. Make choice, explore recursively, undo choice (backtrack). Use when searching permutations, combinations, or paths.

Implementation

def permute(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path)
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
    backtrack([], nums)
    return result

Complexity Analysis

Time Complexity

O(n!)

Space Complexity

O(n)

Key Learning Points

Recursive explorationUndo/backtrack stepUseful for all permutations/combinations