LC 39 & LC 40 (with template)

Solution to LeetCode 39 Combination Sum, LeetCode 40 Combination Sum II.

LeetCode 39

Combination Sum (Medium) [link]

Note that same number can be repeatedly chosen.

For the vertical iteration, the stop criteria of recursion is 1) sum equals to the target 2) sum is larger than the target. For the horizontal iteration, in the first layer, we have n choices, from the first number to the last number, so the number of branches is n. In the first branch, we can only select number from n numbers (starting from the first number). In the second branch, we can only select number from n-1 numbers (starting from the second number). Note that we can select the same number. This pattern stays the same for other layers until the stoping criteria is satisfied.

Time complexity (loose): O(n*2^n). For n positions of the result, we choose or not choose a value. The space complexity is O(target), depending on the depth the recursion tree.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        SUM = 0
        def backtrack(candidates, target, SUM, start):
            if sum(path) > target:
                return

            if sum(path) == target:
                res.append(path[:])
                return 
            
            for i in range(start, len(candidates)):
                SUM += candidates[i]
                path.append(candidates[i])
                backtrack(candidates, target, SUM, i)
                SUM -= candidates[i]
                path.pop()

        backtrack(candidates, target, SUM, 0)
        return res

There are two optimizations: 1] when we determine whether sum > target , we already go into the next round of recursion. However, we don’t need to go to the next round of recursion if we determine sum + candidate[i] > target in advance. To implement this optimization, we add one line of code to return the back track function before going into the next round. 2] Notice that if we implement (1), we have to make sure that the candidate lists is sorted, because when we stop the next recursion, we are ignoring all the values after that node.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        SUM = 0
        def backtrack(candidates, target, SUM, start):
            if sum(path) == target:
                return res.append(path[:])

            for i in range(start, len(candidates)):
                if SUM + candidates[i] > target: 
                      return

                SUM += candidates[i]
                path.append(candidates[i])
                backtrack(candidates, target, SUM, i) # number can repeat
                SUM -= candidates[i]
                path.pop()
        candidates = sorted(candidates)
        backtrack(candidates, target, SUM, 0)
        return res

LeetCode 40

Combination Sum II (Medium) [link]

Note that each number in the candidates list can only be used once in the combination, and there could be duplicates in the candidates list. The difficulty is that there are duplicates in the list but we cannot have duplicated combinations in the result. So the key is that we remove duplicates in the same layer, and do not remove duplicates in the same branch.

Time complexity (loose): O(n*2^n). N is the length of candidates. We need O(n) time to store each combination. There are O(2^n) number of combinations.

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        SUM = 0
        def backtrack(candidates, target, SUM, start):
            if sum(path) == target:
                return res.append(path[:])

            for i in range(start, len(candidates)):
                if SUM + candidates[i] > target: return
                if i > start and candidates[i] == candidates[i-1]: continue

                SUM += candidates[i]
                path.append(candidates[i])
                backtrack(candidates, target, SUM, i+1) # same number cannot be used twice
                SUM -= candidates[i]
                path.pop()
        candidates = sorted(candidates)
        backtrack(candidates, target, SUM, 0)
        return res

Template of Combination and Permutation

Combination(n, d)

def Combination(nums, d, n, s, path, ans):
      if d == n:
          ans.append(path)
        return
      
    for i in range(s, len(nums)):
          path.push(nums[i])
        Combination(nums, d+1, n, i+1, path, ans)
        path.pop()

Permutation(n, d)

def Permutation(nums, d, n, used, path, ans):
      if d == n:
          ans.append(path)
        return
    
    for i in range(0, len(nums)):
          if used[i]: continue
        used[i] = True
        path.push(nums[i])
        Permutation(nums, d+1, n, path, ans)
        path.pop()
        used[i] = False