Python 알고리즘 인터뷰 - 문제 36. 조합의 합

leetcode 46. Permutations - https://leetcode.com/problems/permutations/description/

 

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

 

예제1

입력

candidates = [2,3,6,7], target = 7

출력

[[7], [2,2,3]]

 

예제2

입력

candidates = [2,3,5], target = 8

출력

[

[2,2,2,2],

[2,3,3],

[3,5]

]

 

풀이

조합의 합을 구하는데 중복된 값을 허용하는 케이스이다. 35. 조합 문제를 응용하여 문제를 접근한다. 

먼저 중복된 조합을 허용하므로 dfs는 현재 인덱스를 시작점으로 탐색을 진행한다.

완료 조건으로는 조합의 합이 target과 같거나 target을 초과했을 경우이다. 합이 같을 경우 results에 값을 추가한다.

전체 코드는 다음과 같다.

def combinationSum(candidates, target):
    results = []

    def dfs(start, path: list, sum_comb):
        if sum_comb > target:
            return
        elif sum_comb == target:
            results.append(path)
            return

        for i in range(start, len(candidates)):
            dfs(i, path + [candidates[i]], sum_comb + candidates[i])

    dfs(0, [], 0)

    return results