[LeetCode] Combination Sum | DFS | 파이썬 알고리즘 인터뷰, 정답, 소스코드

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

https://leetcode.com/problems/combination-sum/

Combination Sum - LeetCode

---

문제 요약

• 정수리스트가 주어질 때 원소들을 더하여 target이 되는 원소리스트를 구하라. 
• 각 원소는 중복으로 사용할 수 있다

---

핵심 알고리즘

• BFS로 중복조합 구하기
• 인자값 : 현재까지 더한 원소 리스트, target까지 남은 값, 여태까지 사용한 인덱스의 최대값
• 만약 target까지 남은 값이 0이면 answer에 추가
• 중복을 방지하기 위해 새로운 원소를 추가할 때는 여태까지 사용한 인덱스의 최대값보다 작은 값은 사용하지 않음
• 만약 target까지 남은 값이 추가할 수 있는 원소보다 작으면 즉시 탐색 중단(candidates는 정렬이 되어있어야 함)

---

소스코드

class Solution:
    def combinationSum(self, candidates: [int], target: int) -> [[int]]:
        candidates.sort()
        answer = []

        def dfs(nums: [int], remaining: int, index):
            if remaining == 0:
                answer.append(nums)
                return

            for i in range(index, len(candidates)):
                if remaining < candidates[i]:
                    return

                dfs(nums+[candidates[i]], remaining - candidates[i], i)

        dfs([], target, 0)

        return answer