문제
고유한 정수 배열 candidates와 정수 target이 주어졌을 때, 선택한 숫자의 합이 target이 되는 모든 고유한 candidates 조합을 반환합니다. 조합의 순서는 상관없습니다.
candidates에서 같은 숫자를 횟수 제한 없이 선택할 수 있습니다. 선택한 숫자 중 하나 이상의 빈도가 다른 경우 두 가지 조합은 고유합니다.
테스트 케이스는 주어진 입력에 대해 목표에 합산되는 고유 조합의 수가 150개 미만이 되도록 생성됩니다.
풀이
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result, nums = [], []
def dfs(start, total):
if total > target:
return
if total == target:
return result.append(nums[:])
for i in range(start, len(candidates)):
num = candidates[i]
nums.append(num)
dfs(i, total + num)
nums.pop()
dfs(0, 0)
return result
Back Tracking
백트래킹 기법은 조건을 만족하지 않는 경우 해당 경로를 더이상 탐색하지 않는다. 가지치기(pruning) 와도 같다.
구현하고자 하는 탐색 방식에서 조건문을 추가해 노드의 유망성(promising) 을 판단하고 그렇지 않은 경우 빠져나간다.
참고
백준 N-Queen 문제가 백트래킹의 대표적인 문제라고 한다. 도전해 보자.
