LeetCode 39 - Combination Sum

이 문제는 정수 배열과 target이 주어졌을 때, 합이 target이 되는 모든 조합을 찾는 Medium 난이도 문제다. 같은 숫자를 여러 번 사용할 수 있고, 같은 조합은 한 번만 반환해야 하므로 backtracking으로 현재 조합을 만들고 되돌리는 방식으로 풀었다.

문제 링크 & 설명

문제 링크: 39. Combination Sum
요약: 서로 다른 양의 정수로 이루어진 candidates와 정수 target이 주어졌을 때, 합이 target이 되는 모든 unique combination을 반환하는 문제.

예를 들어 입력이 이렇게 주어진다고 해보자.

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

가능한 조합은 다음과 같다.

[2, 2, 3]
[7]

여기서 중요한 조건은 같은 숫자를 여러 번 사용할 수 있다는 점이다. 2를 한 번만 쓰는 것이 아니라, 같은 후보 숫자 2를 반복해서 선택할 수 있다. 반대로 [2, 3, 2]와 [2, 2, 3]처럼 순서만 다른 조합은 같은 조합으로 봐야 한다.

그래서 이 문제는 조합을 만들되, 선택 순서를 일정하게 유지해서 중복 조합을 만들지 않는 것이 핵심이다.

접근 방법

1. 현재 조합과 남은 합을 들고 내려가기

backtracking에서는 현재까지 선택한 숫자들을 path에 담고, 아직 채워야 하는 값을 remain으로 관리했다.

path   = 현재까지 선택한 숫자 조합
remain = target에서 path의 합을 뺀 남은 값

remain이 0이 되면 현재 path의 합이 target과 같다는 뜻이므로 정답에 추가한다.

if remain == 0:
    answer.append(path[:])
    return

2. start index로 중복 조합 막기

같은 숫자를 여러 번 사용할 수 있으므로, 다음 재귀 호출에서 현재 인덱스를 다시 넘긴다.

self.backtrack(candidates, remain - candidates[i], i, path, answer)

만약 i + 1을 넘기면 현재 숫자를 다시 사용할 수 없다. 이 문제에서는 같은 candidate를 반복 선택할 수 있어야 하므로 i를 그대로 넘긴다.

대신 이전 인덱스로 돌아가지는 않는다. start_index부터 뒤쪽 후보만 확인하기 때문에 조합의 순서가 항상 한 방향으로 유지된다.

[2, 2, 3]은 만들 수 있음
[2, 3, 2]는 만들지 않음
[3, 2, 2]도 만들지 않음

이렇게 하면 같은 값 조합이 순서만 바뀌어서 여러 번 들어가는 일을 막을 수 있다.

3. 정렬 후 가지치기

candidates를 먼저 정렬하면 remain보다 큰 값이 나온 순간 뒤쪽 후보도 더 볼 필요가 없다.

candidates.sort()

정렬된 상태에서 candidates[i]가 remain보다 크다면, 그 뒤의 값들도 모두 remain보다 크거나 같다. 그래서 바로 break할 수 있다.

if remain < candidates[i]:
    break

이 조건은 정답 여부를 바꾸지는 않지만, 더 내려가도 target을 만들 수 없는 가지를 미리 끊어준다.

4. 선택하고 되돌리기

각 후보에 대해 할 일은 단순하다. 현재 값을 path에 넣고, 남은 값을 줄여서 재귀 호출을 한 뒤, 호출이 끝나면 path에서 다시 뺀다.

path.append(candidates[i])
self.backtrack(candidates, remain - candidates[i], i, path, answer)
path.pop()

append는 현재 후보를 선택하는 단계이고, pop은 다음 후보를 시도하기 위해 상태를 되돌리는 단계다. 이 되돌리는 과정이 없으면 다음 조합을 만들 때 이전 선택이 남아 있게 된다.

트러블 슈팅

처음 구현에서는 합이 target과 같아졌을 때 path를 그대로 answer에 넣었다.

if remain == 0:
    answer.append(path)
    return

재귀가 끝난 뒤 결과를 확인해보니, 정답으로 찾았던 조합이 남아 있지 않고 빈 리스트로 바뀌어 있었다. answer에 저장된 값과 탐색에 사용하는 path가 같은 리스트 객체를 가리키고 있었기 때문이다. 정답을 찾은 뒤에도 backtracking 과정에서 path.pop()이 계속 실행되면서 answer 안에서 참조하던 리스트까지 함께 바뀌었다.

정답을 찾은 순간의 원소를 별도 리스트에 저장하도록 얕은 복사본을 넣어서 해결했다.

answer.append(path[:])

슬라이싱 대신 copy()를 사용해도 동작은 같다. path에는 정수만 들어 있으므로 두 방법 모두 현재 원소를 새 리스트에 복사하기에 충분하다.

answer.append(path.copy())

복잡도 분석

시간 복잡도: O(N^(T/M))
- N은 candidates의 길이, T는 target, M은 candidates의 최솟값이다. 한 경로에서 가장 깊게 내려갈 수 있는 횟수는 target을 최솟값으로 계속 줄일 때의 T / M이고, 각 깊이에서 최대 N개의 후보를 시도할 수 있다. 실제 탐색 수는 정렬 후 가지치기와 remain 조건에 따라 줄어든다.
공간 복잡도: O(T/M)
- 재귀 호출 스택과 path의 최대 길이는 target을 최솟값으로 계속 채울 때의 깊이인 T / M에 비례한다. 반환해야 하는 answer 배열은 정답 개수에 비례하는 별도 출력 공간이다.

구현 코드

최종 코드는 candidates를 정렬한 뒤, start_index와 remain을 들고 backtracking을 수행하는 방식이다.

from typing import List

class Solution:
    def backtrack(
        self,
        candidates: List[int],
        remain: int,
        start_index: int,
        path: List[int],
        answer: List[List[int]],
    ) -> None:
        if remain == 0:
            answer.append(path[:])
            return

        for i in range(start_index, len(candidates)):
            if remain < candidates[i]:
                break

            path.append(candidates[i])
            self.backtrack(candidates, remain - candidates[i], i, path, answer)
            path.pop()

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        answer = []

        candidates.sort()
        self.backtrack(candidates, target, 0, path, answer)

        return answer

요약 및 회고

Combination Sum은 가능한 조합을 모두 탐색해야 하므로 backtracking이 맞는 구조였다. 다만 탐색 범위가 빠르게 커질 수 있어서, 불필요한 재귀 호출을 어디에서 끊을 수 있는지도 함께 확인해야 했다. start_index로 선택 순서를 고정해 중복 조합을 막았고, candidates를 정렬한 뒤 remain보다 큰 값에서 탐색을 중단해 더 진행할 수 없는 가지를 줄였다.