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

Backtracking: build permutation by adding unused elements one by one, backtrack after exploring each choice.

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

Time:O(n! * n)

Space:O(n)

Hints

1.Each position can be filled by any remaining element
2.Backtrack after trying each choice
3.n! total permutations

Asked at

Google