[Backtracking: Combinations]: 39. Combination Sum ★

39. Combination Sum

 

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def backtrack(start, comb, total):
            # Base case: 합이 target과 같으면 결과에 추가
            if total == target:
                res.append(comb.copy())
                return
            # 합이 target을 초과하면 더 이상 탐색하지 않음
            if total > target:
                return

            # 후보 숫자들을 하나씩 추가하며 탐색
            for i in range(start, len(candidates)):
                comb.append(candidates[i])  # 현재 숫자 추가
                backtrack(i, comb, total + candidates[i])  # 재귀 호출 (중복 사용 가능)
                comb.pop()  # 백트래킹: 마지막 추가된 숫자 제거

        backtrack(0, [], 0)  # 초기화: start=0, comb=[], total=0
        return res

 

주요 수정 사항

1. 중복 방지:
   • for i in range(start, len(candidates))를 사용하여 현재 인덱스부터 탐색합니다.
   • 이를 통해 이미 고려한 숫자는 다시 탐색하지 않도록 합니다.
2. 누적 합 관리:
   • 매번 sum(comb)을 계산하는 대신, total 변수로 현재까지의 합을 누적합니다.
   • 이렇게 하면 효율성이 크게 향상됩니다.
3. 조기 종료:
   • if total > target: 조건을 추가하여, 목표 값을 초과하면 더 이상 탐색하지 않도록 합니다.

 

start의 역할

start는 백트래킹에서 탐색의 시작 지점을 나타내는 인덱스입니다.

이를 통해 조합 문제에서 중복 조합을 방지하거나, 특정 탐색 순서를 유지할 수 있습니다.

1. 중복 방지:
   • 백트래킹 과정에서 이미 처리한 후보 숫자를 다시 처리하지 않도록, 탐색 시작 지점을 제한합니다.
   • 예를 들어, [2, 3]과 [3, 2]처럼 순서만 다른 중복 조합이 생기지 않도록 합니다.
2. 순서 보장:
   • 후보 숫자들은 항상 현재 선택한 숫자 또는 이후의 숫자만 선택됩니다.
   • 이렇게 하면 숫자가 항상 정렬된 순서로 선택되며, 불필요한 중복 탐색을 줄일 수 있습니다.

요약

1. 현재 인덱스부터 탐색: start 매개변수를 추가하여 중복 방지.
2. 누적 합 변수 사용: total로 현재 합을 관리하여 효율성 향상.
3. 조기 종료 조건: if total > target:으로 불필요한 탐색 차단.

 

좀 더 최적화: total 제거

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(subset, idx):
            # 현재 부분 집합의 합이 target을 초과하면 탐색 종료
            if sum(subset) > target:
                return

            # 현재 부분 집합의 합이 target과 같으면 결과에 추가
            if sum(subset) == target:
                res.append(subset.copy())
                return

            # 각 후보 숫자를 순차적으로 탐색
            for i in range(idx, len(candidates)):
                subset.append(candidates[i])  # 후보 숫자를 포함
                dfs(subset, i)  # 같은 숫자를 다시 선택할 수 있으므로 `i`를 유지
                subset.pop()  # 상태 복구

        dfs([], 0)
        return res

 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 같은 숫자도 여러번. 무제한 선택 가능, The same number may be chosen from candidates an unlimited number of times. 
        
        res = []

        def dfs(subset, idx):    
            if sum(subset) > target:                
                return

            if sum(subset) == target:
                res.append(subset.copy())
                return 

            for i in range(idx, len(candidates)):
                subset.append(candidates[i])
                dfs(subset, i) # 같은숫자도 선택가능하므로.
                subset.pop()

        dfs([], 0)
        return res

 

이 문제는 백트래킹(Backtracking) 을 이용해 푸는 전형적인 조합 탐색 문제입니다.
핵심은:

---

✅ 문제 핵심 요약

• 같은 숫자를 여러 번 사용할 수 있음 (unlimited)
• 중복 조합은 허용하지 않음
• 결과는 순서 상관없이, 합이 정확히 target이 되는 모든 조합

---

✅ 풀이 아이디어

• 백트래킹으로 현재까지 선택한 숫자들의 합이 target이 되면 결과에 추가
• 한 숫자는 여러 번 선택 가능하므로, 같은 인덱스를 재귀 호출 시 다시 넘길 수 있음 (start 유지)
• target을 초과하면 가지치기 (더 이상 탐색 안 함)

class Solution:
    def combinationSum(self, candidates, target):
        res = []

        def backtrack(start, path, total):
            if total == target:
            	res.append(path.copy()) # res.append(list(path))  # 정답 조합 저장                 
                return
            if total > target:
                return  # 가지치기

            for i in range(start, len(candidates)):
                path.append(candidates[i])  # 숫자 선택
                backtrack(i, path, total + candidates[i])  # 같은 숫자 다시 선택 가능 → i
                path.pop()  # 백트래킹

        backtrack(0, [], 0)
        return res

 

최종 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # combination 찾는데, 합이 target 인 조합

        res = []  # 결과 조합들을 저장할 리스트

        def help(i, candidates, target, curComb, res):
            # 현재까지의 조합의 합이 target과 같다면 정답 후보로 추가
            if sum(curComb) == target:
                res.append(curComb.copy())  # 현재 조합 복사하여 저장
                return  # 조건 만족했으므로 재귀 종료

            # 합이 target 보다 클때도 끝나야 함!! <-- 아주 중요
            # 또는 인덱스가 candidates 범위를 벗어난 경우도 종료
            if i >= len(candidates) or sum(curComb) > target: 
                return  # 조건을 초과했으므로 백트래킹 종료

            curComb.append(candidates[i])  # 현재 숫자를 조합에 포함

            # 현재 숫자를 무제한으로 여러번 넣을수 있음
            # 그래서, i+1이 아니라 i를.. <-- 아주 중요!!
            # i를 그대로 넣는 이유는 같은 숫자를 다시 선택 가능하기 때문
            help(i, candidates, target, curComb, res)  # 같은 숫자를 계속 포함시킬 수 있음

            curComb.pop()  # 백트래킹: 마지막에 추가한 숫자 제거

            help(i+1, candidates, target, curComb, res)  # 다음 숫자로 넘어가기

        help(0, candidates, target, [], res)  # 탐색 시작: 인덱스 0부터, 현재 조합은 빈 리스트
        return res  # target을 만드는 모든 조합 반환

 

📌 핵심 포인트 요약

• sum(curComb) == target → 정답 조합임
• sum(curComb) > target 또는 i >= len(candidates) → 실패 케이스 → 더 이상 진행 X
• 같은 숫자를 여러 번 사용할 수 있으므로 i를 유지한 채 재귀 호출