[그래프] 조합의 합

 

39 | Combination Sum
https://leetcode.com/problems/combination-sum/

 

 

 

 

 

작성 코드

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        prev_elements = []
        def dfs(cnt, elements):
            if len(prev_elements) == cnt:
                if sum(prev_elements) == target:
                    results.append(prev_elements[:])
                return
            for cand in elements:
                prev_elements.append(cand)
                dfs(cnt, candidates[candidates.index(cand):])
                prev_elements.pop()
        for cnt in range(1, target // min(candidates) + 1):
            dfs(cnt, candidates)

        return results

 

• 한 원소를 중복해서 계속 뽑을 수도 있으므로 조합 배열의 개수는 무제한으로 늘어남, candidates 에서 가장 작은 값으로 target 을 나눔으로써 배열 범위 축소
• ex) target = 8, candidates = [2, 3, 4] 라면 target 값을 만족하기 위해서는 가장 작은 원소인 2를 4번 써야함, 5번 이상은 가장 작은 원소인 2를 5번 써도 target 값을 넘어가버림

 

• prev_elements의 길이와 원소의 개수인 cnt가 같고, prev_elements의 합과 target 이 같다면 result에 append
• elements(앞으로 방문할 원소)를 돌면서 먼저 cand를 prev_elements(방문한 원소)에 append, dfs의 파라미터로 현재 candidate 이후로 리스트 슬라이싱 해서 넘겨줌 ( -> 원소가 distinct 하기 때문 ), 다 돌면 pop() 해줌

 

• 문제 자체는 통과했으나 실행 시간이 오래걸림

 

 

이상 코드

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        def dfs(csum, index, path):
            # Termination condition
            # csum value is exceeded target vaule
            if csum < 0:
                return
            # target value and csum match
            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

 

• dfs 함수 파라미터 csum - candidate_sum 합을 갱신해 나감, index - 순서, path - 지금까지의 탐색 경로
• 종료 조건 (1) 목표값 초과, (2) 목표값 만족
• 현재 index 부터 candidates 를 돌면서 csum - candidates[i], path + [candidates[i]] (배열이기 때문에) 를 넘겨줌

 

 

핵심

 

• 종료 조건을 단순화