39. Combination Sum

 1class Solution:
 2    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
 3        result = []
 4        n = len(candidates)
 5
 6        def bt(start: int, r_cand: List[int], r_sum: int):
 7            if r_sum == target:
 8                result.append(r_cand[:])
 9            elif r_sum < target:
10                for i in range(start, n):
11                    cand_i = candidates[i]
12                    r_cand.append(cand_i)
13                    bt(i, r_cand, r_sum + cand_i)
14                    r_cand.pop()
15
16        bt(0, [], 0)
17
18        return result