[LeetCode] #39. Combination Sum (python)

문제

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

Combination Sum - LeetCode

숫자 집합 candidates의 원소들을 조합해서 합한 값이 target이 되는 조합들을 반환해야 한다. 원소들은 중복 사용이 가능하다.

 

예시 입출력

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

 

 

풀이

 

내 풀이

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        output=[]
        
        def dfs(elements, big, result):
                       
            if result==0:
                output.append(elements[:])
                return
        
            for can in candidates:
                if can>result or can>big:
                    continue
                elements.append(can)
                dfs(elements, can,result-can)
                elements.pop()
        
        
        for can in reversed(candidates):
            dfs([can], can, target-can)
        
        return output

큰 값부터 탐색하기 위해서 reversed(candidates)를 사용했다. 이미 추가된 값보다 큰 값은 사용하지 않기 위해 dfs 함수에 big 인자를 넣었다. result는 target 값이 되었는지 확인하기 위한 인자다. target에서 추가한 값을 뺀 값을 넘긴다. elements는 조합이 추가되는 리스트다.

dfs 함수

result가 0이면 target 값이 된 것이므로 output에 조합을 추가한다.

candidates에서 result보다 값이 크거나 최대값보다 큰 값이면 continue로 넘어간다. 그렇지 않으면 elements에 추가하고 dfs함수를 재귀호출한다. pop은 elements에 들어간 값을 빼는 역할을 한다.

 

 

책 풀이

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

dfs 함수 파라미터

첫번째 파라미터 : 합 갱신 변수

두번째 파라미터 : 순서

세번째 파라미터 : 탐색 경로

 

dfs 함수 종료 조건

1. 목표값을 초과한 경우
2. 목표값에 도달한 경우

 

참고한 책 : 파이썬 알고리즘 인터뷰