[파이썬 알고리즘 인터뷰] 36. 조합의 합

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

36. 조합의 합

leetcode 39. Combination Sum 문제입니다.

leetcode.com/problems/combination-sum/

 

 

풀이

dfs와 백트래킹을 활용한 풀이법입니다.

def combinationSum(self, candidates,target):
    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