문제 개요
중복되지 않은 후보 숫자들로 이루어진 집합과 하나의 목표 숫자가 주어졌다고 가정해 봅시다. 우리가 찾아야 할 것은 후보 숫자들을 더했을 때 목표 값이 되는 모든 고유한 조합입니다. 특별한 규칙이 하나 있는데, 동일한 숫자는 무제한으로 반복해서 선택할 수 있다는 점입니다.
예를 들어 후보 숫자가 [2, 3, 6, 7]이고 목표 값이 7이라면, 가능한 결과는 다음과 같습니다.
[[7], [2, 2, 3]]
7 자체가 후보에 포함되어 있으므로 [7]이 답이 되고, 2를 세 번 더하고 3을 한 번 더하면 7이 되므로 [2, 2, 3]도 유효한 조합입니다.
해결 접근 방법: 재귀와 백트래킹
이 문제는 재귀(recursion)와 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 재귀 함수의 이름을 solve()라고 하겠으며, 이 함수는 다음 인자들을 받습니다.
- 결과를 저장할 배열(res)
- 이미 발견한 조합의 중복 여부를 기록하는 맵(unique)
- 남은 목표 값(target)
- 중복이 제거된 후보 숫자 리스트(candidates)
처음에는 결과 배열과 맵이 모두 비어 있는 상태에서 시작합니다. solve() 함수의 동작 흐름은 다음과 같습니다.
- 목표 값이 0인 경우: 현재까지 선택된 원소들로 임시 리스트(temp)를 만듭니다. 이 리스트를 정렬한 뒤 튜플로 변환하여 맵에 존재하지 않는지 확인합니다. 새로운 조합이라면 맵에 등록하고 결과 배열에 추가한 후 반환합니다.
- 목표 값이 0보다 작은 경우: 더 이상 진행할 수 없으므로 즉시 반환합니다(백트래킹).
- 그 외의 경우: 현재 인덱스 i부터 후보 리스트의 끝까지 반복하면서 각 원소를 현재 조합(current)에 추가하고, 목표 값에서 해당 원소를 뺀 값으로 재귀 호출을 수행합니다. 재귀 호출이 끝나면 마지막에 추가한 원소를 제거하여 다른 경로를 탐색할 수 있도록 합니다.
여기서 중요한 포인트는 재귀 호출 시 시작 인덱스를 i로 유지한다는 것입니다. 이렇게 하면 같은 숫자를 반복해서 사용할 수 있으면서도, 이미 지나간 숫자를 다시 앞쪽에서 선택하는 중복 조합의 생성을 방지할 수 있습니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution(object):
def combinationSum(self, candidates, target):
result = []
unique = {}
candidates = list(set(candidates))
self.solve(candidates, target, result, unique)
return result
def solve(self, candidates, target, result, unique, i=0, current=[]):
if target == 0:
temp = [i for i in current]
temp1 = temp
temp.sort()
temp = tuple(temp)
if temp not in unique:
unique[temp] = 1
result.append(temp1)
return
if target < 0:
return
for x in range(i, len(candidates)):
current.append(candidates[x])
self.solve(candidates, target - candidates[x], result, unique, i, current)
current.pop(len(current) - 1)
ob1 = Solution()
print(ob1.combinationSum([2, 3, 6, 7, 8], 10))입력
[2, 3, 6, 7, 8] 10
출력
[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]
동작 방식 요약
위 실행 결과를 보면 목표 값 10을 만드는 다섯 가지 조합이 모두 출력됩니다. 각 조합은 다음과 같이 검증할 수 있습니다.
- [2, 8] → 2 + 8 = 10
- [2, 2, 2, 2, 2] → 2 × 5 = 10
- [2, 2, 3, 3] → 2 + 2 + 3 + 3 = 10
- [2, 2, 6] → 2 + 2 + 6 = 10
- [3, 7] → 3 + 7 = 10
이 알고리즘은 최악의 경우 지수적인 시간 복잡도를 가질 수 있지만, 백트래킹을 통해 목표 값을 초과하는 경로를 조기에 차단하기 때문에 실제로는 상당히 효율적으로 동작합니다. 또한 맵을 활용해 중복 조합을 걸러내므로, 결과에 동일한 조합이 여러 번 포함되는 일은 없습니다.