[알고리즘][그래프] - 5. 조합의 합

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/combination-sum/submissions/

숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라 각 원소는 중복으로 나열 가능하다.

---

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

        result = []

        def DFS(csum, index, path):
            #목표값 초과한 경우 탐색 종료
            if csum < 0:
                return
            if csum == 0:
                result.append(path)
                return

            for i in range(index, len(candidates)):
                DFS(csum - candidates[i], i, path + [candidates[i]])

        DFS(target, 0, [])
        return result