39. Combination Sum

이렇게 찾을때까지 쭉 타는 방식으로 해결하면됨

class Solution:
    def combinationSum(self, candidates, target):
        def dfs(index, cur_sum):
            # 초과하면 종료
            if cur_sum > target:
                return
            # 찾으면 종료
            if cur_sum == target:
                answer.append(cur[:])
                return

            for i in range(index, len(candidates)):
                cur.append(candidates[i])
                cur_sum += candidates[i]
                dfs(i, cur_sum)
                cur.pop()
                cur_sum -= candidates[i]

        answer = []
        cur = []

        dfs(0, 0)

        return answer