LC 78 & LC 90

Solution to LeetCode 78 Combinations and LeetCode 90 Subsets II.

LeetCode 78

Combinations. (Medium) [link]

We are going to store all nodes in the recursion tree rather than only the leaves. In the implementation, we collection path before stopping recursion, to make sure every node is collected into the result list.

The stopping criteria is when the length of the path is equal to the length of the candidate list. So we simply iterate the nums list by using for loop and no other stopping criteria needed within the for loop.

The time complexity is O(n*2^n). There are O(2^n) combinations of a list of length n. Thinking of every number in the list can be chosen or not be chosen. It takes O(n) time to generate each list.

The space complexity is O(n), which is the space taken by path.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

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

            for i in range(start, len(nums)):
                # no stopping criteria
                path.append(nums[i])
                backtrack(nums, i+1)
                path.pop()

        backtrack(nums, 0)
        return res

LeetCode 90

Subsets II (Medium) [link]

There could be duplicates in the input list, but we do not want duplicated combinations in the result list. In the same level of the recursion tree, that is the for loop in the recursion function, we need to skip the duplicates. That also requires us to sort the input list in advance so as to easily determine duplicates.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        path = []

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

            for i in range(start, len(nums)):
                # stopping criteria
                if i > start and nums[i] == nums[i-1]:
                    continue 
                path.append(nums[i])
                backtrack(nums, i+1)
                path.pop()
        
        nums = sorted(nums)
        backtrack(nums, 0)
        return res