Backtracking: 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