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

 

<--- 리트코드 39. Combination Sum --->

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

 

입력

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

출력

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

 

입력

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

출력

[   [2,2,2,2],   [2,3,3],   [3,5] ]

 

 

# 풀이

1. DFS로 중복 조합 그래프 탐색

def combination_sum(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
 
candidates = [2,3,6,7]
target = 7
 
print(combination_sum(candidates, target))