Permutations

Solution

Backtracking 1

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

    def dfs(nums, path):
        if not nums:
            res.append(path)
        for i in range(len(nums)):
            dfs(nums[:i] + nums[i+1:], path + [nums[i]])

    dfs(nums, [])
    return res

Backtracking 2

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

    def dfs(fst):
        # if all integers are used up
        if fst == n:
            res.append(nums[:])
        for i in range(fst, n):
            # place i-th integer first in the current permutation
            nums[fst], nums[i] = nums[i], nums[fst]
            # use next integers to complete the permutations
            dfs(fst + 1)
            # backtrack
            nums[fst], nums[i] = nums[i], nums[fst]

    dfs(0)
    return res