LeetCode

LeetCode 39 Combination Sum 풀이: 중복 없는 백트래킹 조합 탐색

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

후보 숫자를 여러 번 사용할 수 있는 모든 조합을 찾아야 한다. [2, 3]과 [3, 2]처럼 순서만 다른 경우 하나로 처리해야 한다. 재귀 상태에서 선택 가능한 범위를 관리하고 선택을 되돌리는 백트래킹이 필요하므로 Level 3으로 판단했다.

1. 문제 요약

서로 다른 정수로 이루어진 candidates와 목표 합 target이 주어진다. 후보 숫자를 원하는 만큼 선택해 target이 되는 모든 조합을 반환해야 한다.

중요한 조건은 다음과 같다.

  • candidates의 원소는 서로 다르다.
  • 하나의 후보 숫자를 여러 번 사용할 수 있다.
  • 숫자의 선택 순서만 다른 조합은 같은 조합이다.
  • 결과 조합의 순서는 어떤 순서여도 된다.
  • 후보 개수는 최대 30, 후보 값은 2 이상 40 이하다.
  • target은 최대 40이다.

예를 들어 candidates = [2, 3, 6, 7], target = 7이면 [2, 2, 3]과 [7]을 반환한다. [3, 2, 2]는 숫자 선택 순서만 다르므로 별도의 결과로 추가하지 않는다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

후보 생성과 검증

후보를 오름차순으로 정렬하고, 재귀 함수가 현재 인덱스 start부터 후보를 선택하도록 한다. 재귀 상태는 다음과 같다.

  • start: 이번 조합에서 선택할 수 있는 첫 후보의 인덱스
  • path: 현재까지 선택한 숫자 목록
  • remaining: target까지 남은 합

각 인덱스 i에 대해 후보를 선택하면 path에 추가하고 dfs(i, ...)를 호출한다. 같은 i를 다시 전달하는 이유는 같은 숫자를 여러 번 사용할 수 있기 때문이다. 선택을 마친 뒤 마지막 원소를 제거하고 다음 후보를 시도한다.

선택: candidates[i]를 path에 추가하고 다시 i부터 탐색
복귀: path에서 candidates[i]를 제거
다음 선택: i + 1부터 탐색

remaining == 0이면 현재 path가 정확한 조합이므로 결과에 복사해 저장한다. remaining < 0이 되면 합이 이미 목표를 초과했으므로 해당 경로를 종료한다.

후보 인덱스를 유지해 조합 순서를 고정하기

재귀 호출에서 항상 현재 인덱스 이상의 숫자만 선택하면 조합의 숫자가 오름차순으로 만들어진다. 따라서 [2, 3]을 만든 뒤 [3, 2]를 다시 만드는 경로는 생성되지 않는다.

반면 후보를 선택한 뒤 i + 1부터만 탐색하면 같은 숫자의 재사용되지 않는다. 이 문제에서는 선택한 후보의 인덱스를 그대로 다음 호출에 전달해야 [2, 2, 3]과 같은 조합을 만들 수 있다.

가지치기와 경계 처리

후보를 정렬했기 때문에 현재 candidates[i]를 더했을 때 remaining보다 크다면, 이후 후보도 모두 더 크다. 따라서 그 시점에서 반복을 중단해도 된다.

if candidates[i] > remaining:
    break

단순히 remaining < 0이 된 뒤 반환하는 것보다, 같은 레벨에서 확인할 수 없는 더 큰 후보들까지 한 번에 제거한다.

시간·공간 복잡도

출력해야 하는 조합 수 자체가 입력에 따라 달라지므로 정확한 시간은 탐색한 재귀 노드와 결과 크기에 비례한다. m을 가장 작은 후보, T를 목표 합이라고 하면 조합 하나의 최대 깊이는 T / m이고, 최악의 경우 시간 복잡도는 지수적으로 증가할 수 있다.

재귀 깊이와 현재 조합을 제외한 보조 공간은 O(T / m)이며, 정렬된 후보 복사본까지 포함하면 O(n + T / m)이다. 반환 결과를 저장하는 공간은 별도로 결과 조합 전체 크기만큼 필요하다.

3. 문제 해결 코드 (Python)

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates = sorted(candidates)
        result = []

        def dfs(start: int, remaining: int, path: list[int]) -> None:
            if remaining == 0:
                result.append(path.copy())
                return

            for i in range(start, len(candidates)):
                candidate = candidates[i]

                if candidate > remaining:
                    break

                path.append(candidate)
                # i를 그대로 전달해 같은 후보를 다시 사용할 수 있게 함
                dfs(i, remaining - candidate, path)
                path.pop()

        dfs(0, target, [])
        return result

path는 모든 재귀 호출이 공유하는 하므로, 정답에 추가할 때는 path.copy()로 복사해야 함. 복사하지 않고 같은 리스트를 저장하면 이후의 append와 pop에 의해 기존 결과도 바뀐다.

4. 오답 접근과 반례

선택 후 항상 다음 인덱스로 이동하기

후보를 한 번 선택한 뒤 dfs(i + 1, ...)로 이동하면 같은 숫자를 재사용할 수 없다. 다음 입력에서 2를 여러 번 사용해야 하지만, 이 방식은 [2, 2, 3]을 만들지 못한다.

candidates = [2, 3]
target = 7
정답 = [[2, 2, 3]]

무제한 재사용 조건을 반영하려면 후보를 선택한 다음에도 같은 인덱스 i에서 다시 시작해야 한다.

모든 후보에서 재귀를 다시 시작하기

매 단계마다 후보 배열의 처음부터 선택하면 [2, 3]과 [3, 2]가 모두 생성된다. 두 결과는 문제에서 같은 조합으로 간주하므로, 현재 인덱스보다 앞선 후보를 다시 선택하지 않는 방향 제어가 필요하다.

합이 목표를 넘은 경로를 계속 탐색하기

양수 후보만 주어지므로 현재 합이 목표를 초과한 경로에서는 더해도 목표로 돌아올 수 없다. 이 경로를 계속 탐색하면 정답이 아닌 재귀 호출만 늘어난다. 후보를 정렬하고 현재 후보가 남은 합보다 커지는 순간 반복을 중단하면 같은 레벨의 나머지 후보도 제거할 수 있다.

복사해 실행할 테스트

조합의 출력 순서가 달라져도 비교할 수 있도록 각 조합과 전체 결과를 정렬한다.

solver = Solution()
actual = solver.combinationSum([2, 3, 6, 7], 7)
assert sorted(sorted(items) for items in actual) == [[2, 2, 3], [7]]
assert solver.combinationSum([2], 1) == []

5. 공식 예제와 추가 검증

작성한 combinationSum 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다. 결과 조합의 순서와 각 조합의 원소 순서는 비교를 위해 정렬해 확인했다.

공식 예제

입력 기대 출력 확인 결과
candidates = [2,3,6,7], target = 7 [[2,2,3],[7]] 통과
candidates = [2,3,5], target = 8 [[2,2,2,2],[2,3,3],[3,5]] 통과
candidates = [2], target = 1 [] 통과

추가 검증 1: 하나의 후보를 반복 사용

입력: candidates = [3], target = 9
기대 출력: [[3,3,3]]
확인 결과: 통과
검증 목적: 같은 후보를 여러 번 선택하는지 확인

추가 검증 2: 가능한 조합이 없는 경우

입력: candidates = [2, 4], target = 7
기대 출력: []
확인 결과: 통과
검증 목적: 목표 합을 만들 수 없는 경로를 올바르게 종료하는지 확인

추가 검증 3: 조합 순서 중복 제거

입력: candidates = [2, 3], target = 5
기대 출력: [[2,3]]
확인 결과: 통과
검증 목적: [2,3]과 [3,2]를 하나의 조합으로 처리하는지 확인

6. 다른 풀이 방식 검색 및 비교

재귀에서 현재 후보를 선택하는 경우와 선택하지 않는 경우를 분리하는 방식도 사용할 수 있다. 이 방식은 이진 결정 트리를 명확하게 표현하지만, 후보를 정렬한 뒤 반복문으로 현재 인덱스 이후를 순회하는 방식이 각 단계의 선택을 읽기 쉽고 candidate > remaining 조건으로 가지치기하기 편하다.

이 글의 풀이에서는 같은 후보를 재사용할 때 현재 인덱스를 유지하고, 새로운 후보로 넘어갈 때만 인덱스를 증가시켰다. 이 한 가지 인덱스 규칙이 무제한 재사용과 조합 중복 제거를 동시에 처리한다.

마무리

Combination Sum은 가능한 후보 선택을 모두 탐색하되, 같은 조합을 여러 순서로 만들지 않는 문제다. 현재 인덱스부터만 선택하고 선택한 후보의 인덱스를 재귀에 그대로 전달하면 무제한 재사용을 표현할 수 있다. 후보를 정렬한 뒤 남은 합보다 큰 값에서 탐색을 중단하면 불필요한 경로를 줄이면서 모든 유효한 조합을 반환할 수 있다.

#백트래킹#LeetCode#난이도 3