Combination Sum

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        res = []
        comb = []
        def backtrack(start, s):
            if s > target:
                return
            
            if s == target:
                res.append(comb[:])
                return
            
            for i in range(start, len(candidates)):
                comb.append(candidates[i])
                backtrack(i, s + candidates[i])
                comb.pop()


        backtrack(0, 0)
        return res

 1class Solution:
 2    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
 3        candidates.sort()
 4        res = []
 5        comb = []
 6        def backtrack(start, s):
 7            if s > target:
 8                return
 9            
10            if s == target:
11                res.append(comb[:])
12                return
13
14            for i in range(start, len(candidates)):
15                if i > start and candidates[i-1] == candidates[i]:
16                    continue
17                comb.append(candidates[i])
18                backtrack(i+1, s + candidates[i])
19                comb.pop()
20        
21        backtrack(0, 0)
22        return res

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        comb = []
        def backtrack(s, nxt):
            if s == 0 and len(comb) == k:
                res.append(comb[:])
                return
            
            if s < 0 or len(comb) == k:
                return
            
            for i in range(nxt, 10):
                comb.append(i)
                backtrack(s-i, i+1)
                comb.pop()
            
        backtrack(n, 1)
        return res

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(target+1):
            for num in nums:
                if i - num < 0:
                    continue

                dp[i] += dp[i-num]
        return dp[-1]
        
        # @cache
        # def backtrack(s):
        #     if s == target:
        #         return 1
            
        #     if s > target:
        #         return 0
            
        #     res = 0
        #     for num in nums:
        #         res += backtrack(s+num)
        #     return res
        
        # return backtrack(0)