LC 0039 0040 0216 0377 [M] [M] [M] [M] Combination Sum (Subset Sum) I II III IV - ALawliet/algorithms GitHub Wiki

a combination is a subsets problem because order doesn't matter for both

so this problem is similar to generate Subsets but with more conditions

I

I: The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

BAD

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def helper(path):
            if sum(path) == target:
                if sorted(path) not in coll:
                    coll.append(sorted(path))
            elif sum(path) > target:
                return
            else:
                for i in candidates:
                    helper(path + [i])
        
        coll = []
        helper([])
        return coll

but the trick to get uniques without double sorting is to sort just once at the beginning then keep track of the start index we used so we can scan for any frequency of that first then completely move on to the next digit

GOOD

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def helper(target, start, path):
            if target == 0:
                coll.append(path)
            elif target < 0: # exceed the scope, stop exploration.
                return
            else:
                for i in range(start, len(candidates)):
                    helper(target - candidates[i], i, path + [candidates[i]]) # i not i+1 because we can use many times, give the current number another chance, rather than moving on
        
        coll = []
        helper(target, 0, [])
        return coll

II

II: Each number in candidates may only be used once in the combination.

each number can only be used once so we either exclude or sort and skip dupes

the important difference to Combination Sum I is looping to create many branches for all the numbers vs. just include/exclude and moving to the next idx

BAD (TLE)

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def helper(target, idx, path):
            if target == 0:
                if path not in coll:
                    coll.append(path)
            elif idx == len(candidates):
                return
            elif target < 0:
                return
            else:
                helper(target, idx + 1, path)
                helper(target - candidates[idx], idx + 1, path + [candidates[idx]])
        
        coll = []
        candidates.sort()
        helper(target, 0, [])
        return coll

or we can skip dupes cause it's sorted (USE THIS METHOD)

GOOD

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def helper(target, idx, path):
            if target == 0:
                coll.append(path)
            elif target < 0:
                return
            else:
                for i in range(idx, len(candidates)):
                    if i > idx and candidates[i] == candidates[i-1]: continue # skip dupes
                    helper(target - candidates[i], i+1, path + [candidates[i]]) # i+1 because we can only use once
        
        coll = []
        candidates.sort() # sort to skip dupes
        helper(target, 0, [])
        return coll

III

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(target, i, path):
            if target == 0:
              if len(path) == k:
                res.append(path)
            elif target < 0:
                return
            elif target > 0:
                for i in range(i, 10):
                    dfs(target - i, i + 1, path + [i])
        
        res = []
        dfs(n, 1, [])
        return res

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def helper(target, idx, path):
            if target == 0:
              if len(path) == k:
                coll.append(path)
            elif target < 0:
                return
            else:
                for i in range(idx, 10):
                    helper(target - i, i + 1, path + [i])
        
        coll = []
        helper(n, 1, [])
        return coll

• it's titled wrong, since order matters it's actually a PERMUTATION sum

just like Coin Change 2 (num ways to make change given unlimited denoms) but since this one is a count PERMUTATION sum and coin change is a count COMBINATION sum, the difference is switching the for loops around

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        T = [0] * (target + 1)

        T[0] = 1
       
        for i in range(1, target + 1):
             for n in nums:
                if n <= i:
                  T[i] += T[i-n]

        return T[-1]