[DSA][Backtracking] 03. Combination Sum II

LeetCode 40

 

03. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.

 

[질문하기]

- candidates 배열은 정렬되어 있나요? NO

 

[아이디어]

- Backtracking으로 후보 숫자를 차례대로 선택·취소하며 모든 조합을 탐색하고, 같은 DFS 레벨에서 이전과 같은 숫자는 건너뛰어 중복을 제거한다.

 

 

[풀이 1] Backtracking

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        res, tmp = [], []

        def dfs(idx, s):
            if s == target:
                res.append(tmp[:])
                return
            
            for i in range(idx, n):
                if i > idx and candidates[i] == candidates[i - 1]:
                    continue
                if s + candidates[i] > target:
                    break
                tmp.append(candidates[i])
                dfs(i + 1, s + candidates[i])
                tmp.pop()
        dfs(0, 0)
        return res

Combination Sum II는 기본 Combination Sum과 비교했을 때 candidates 배열에 중복 값이 존재할 수 있다는 것, 각 숫자는 한 번만 사용할 수 있다는 차이가 있다. 2025.11.10 - [자료구조와 알고리즘] - [DSA][Backtracking] 02. Combination Sum

기본 Combination Sum에서는 같은 숫자를 여러 번 선택할 수 있으므로 dfs(i, s + candidates[i])처럼 같은 인덱스(i)를 다시 탐색할 수 있게 했지만, Combination Sum II에서는 한 숫자를 재사용할 수 없기 때문에 dfs(i + 1, s + candidates[i])처럼 다음 탐색은 반드시 다음 인덱스로 넘어가야 한다.

또한, candidates에 같은 값이 여러 개 있으면, 다른 인덱스의 같은 숫자를 선택해도 동일한 조합이 여러 번 만들어질 수 있다. candidates = [1, 1, 2], target = 3이라면 첫 번째 1과 2를 택해도 두 번째 1과 2를 택해도 target = 3이 만들어지므로 중복된 리스트가 답에 포함된다. DFS에서는 각 재귀 호출이 "같은 깊이(level)"에서 선택을 결정하는데, 같은 level 내에서 이미 사용한 숫자가 다시 나오면 이를 skip 한다.i > idx는 같은 level에서 반복문을 진행 중이며, candidates[i] == candidates[i-1]는 바로 이전 숫자와 값이 같은 경우를 의미한다.

 

 

⏱️ 시간복잡도

각 원소는 포함할지 말지 두 가지 선택지를 가지므로, 가능한 조합의 수는 총 2ⁿ개다. 각 부분 집합을 생성할 때 최대 n개의 원소에 대해 Target과 비교해야 하므로, 전체 시간 복잡도는 O(n × 2ⁿ)이다.

🧠 공간복잡도

각 숫자를 최대 한 번만 사용하므로 DFS 깊이는 최대 n이고, 백트래킹에서 현재 만들고 있는 조합도 최대 n개 원소를 가질 수 있으므로 공간 복잡도는 O(n)이다.