LC 46 & LC 47 (Template)

Solution to LeetCode 46 Permutations and LeetCode 47 Permutation II.

LeetCode 46

Permutations (Medium) [link]

The difference between permutations and combinations is that the order matters for permutations. So we need to keep track of the number used in each recursion.

The assumption of using used list or checking whether the current number exists in the path, is that there is no duplicates in the input list.

Time complexity O(n * n!). The number of calling backtrack function is O(n!). It takes O(n) time to store the path result to the result list. The space complexity is O(n).

# Using `used`.
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = []
        path = []

        def backtrack(nums, used):
            if len(nums) == len(path):
                return res.append(path[:])

            for i in range(len(nums)):
                if nums[i] in used:
                    continue
                used.append(nums[i])
                path.append(nums[i])
                backtrack(nums, used)
                used.pop()
                path.pop()

        backtrack(nums, used)
        
        return res

# Not using `used`.
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

        def backtrack(nums):
            if len(nums) == len(path):
                return res.append(path[:])

            for i in range(len(nums)):
                if nums[i] in path:
                    continue
                path.append(nums[i])
                backtrack(nums)
                path.pop()

        backtrack(nums)
        return res

LeetCode 47

Permutations II (Medium) [link]

The additional condition based on LC 46 is that: there could be duplicated numbers. So we need to prune the tree when it leads to duplicated results. We only need to remove duplicates in the for loop. We don’t want to remove duplicates in the recursion rounds. So we do the following two things:

1 We keep track of which number is actually used by used array and skip it in the recursion, so that we make sure we are not repeatedly using any number.

2 In each layer of the recursion tree, we remove duplicates. In the implementation, within for loop, we check duplicate and skip it. Notice that all of the numbers considered in the same layer are not used.

Time complexity O(n * n!). The number of calling backtrack function is O(n!). It takes O(n) time to store the path result to the result list. The space complexity is O(n).

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []
        used = [0]*len(nums)

        def backtrack(nums, used):
            if len(nums) == len(path):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if not used[i]:
                    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                        continue
                    used[i] = 1
                    path.append(nums[i])
                    backtrack(nums, used)
                    path.pop()
                    used[i] = 0

        nums = sorted(nums)
        backtrack(nums, used)
        return res

See how this is different from LeetCode 491.

Template of Recursion

def backtracking(parameters)
    if (stop condition):
        result
        return

    for (choose：elements in current tree level):
        deal with node
        backtracking(path，list) # recursion
        backtrack and retrieve