39. Combination Sum

we can use the recipe, the goal is to find if the sum of current array = sum

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        curr = []
        n = len(candidates)

        def bt(start_i, curr_sum):
            if curr_sum == target:
                res.append(curr.copy())
                return
            if start_i >= n or curr_sum > target:
                return
            for i in range(start_i, n):
                curr.append(candidates[i])
                bt(i, curr_sum + candidates[i])
                curr.pop()
        bt(0, 0)
        return res