[DSA][Backtracking] 02. Combination Sum

LeetCode 39

 

02. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.
You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times.
Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

 

[질문하기]

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

 

[아이디어]

- Backtracking을 사용하여 후보 숫자를 차례대로 선택·취소하며 모든 가능한 조합을 탐색한다.

 

[풀이 1] Backtracking

class Solution:
    def combinationSum(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 s + candidates[i] > target:
                    break
                tmp.append(candidates[i])
                dfs(i, s + candidates[i])
                tmp.pop()
        dfs(0, 0)
        return res

DFS에서 현재 숫자를 조합 리스트에 추가하고 재귀 호출을 통해 다음 숫자를 탐색하며, 재귀가 끝나면 마지막 숫자를 제거해 다른 조합을 시도한다.

후보 배열을 오름차순으로 정렬하면, 현재 합이 target을 초과하는 순간 이후 숫자들도 모두 초과하므로 더 이상 탐색할 필요가 없고, break로 효율적인 가지치기가 가능하다.

 

⏱️ 시간복잡도

target을 t, 배열의 최솟값을 m이라고 하면, 재귀 호출의 최대 깊이는 t/m이다.
각 단계에서 숫자를 선택하거나 선택하지 않는 모든 경우를 탐색하므로, 최악의 시간 복잡도는 O(2^(t/m))이다.

🧠 공간복잡도

재귀 스택과 임시 배열(tmp)에 저장되는 숫자의 최대 개수도 최대 깊이와 같으므로, 공간 복잡도는 O(t/m)이다.