Backtracking: 40. Combination Sum II

40. Combination Sum II

 

https://youtu.be/rSA3t6BDDwg?si=w-QEPd8Mv2Krb5C-

 

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # Sort the candidates to facilitate duplicate removal
        # 후보 숫자를 정렬하여 중복된 숫자를 연속적으로 배치
        candidates.sort()
        
        # To store the final combinations
        # 최종 결과를 저장할 리스트
        res = []        

        # Backtracking function
        # 백트래킹 함수 정의
        def backtrack(subset, idx):
            # If the current sum exceeds the target, terminate this branch
            # 현재 합이 target을 초과하면 종료
            if sum(subset) > target:
                return

            # If the current sum equals the target, add the subset to the result
            # 현재 합이 target과 같으면 결과에 추가
            if sum(subset) == target:
                res.append(subset.copy())  # Add a copy of the current subset
                return

            # Variable to track the previous number for duplicate removal
            # 중복 제거를 위한 이전 숫자 추적 변수
            prev = -1
            for i in range(idx, len(candidates)):
                # Skip duplicate numbers at the same level of recursion
                # 동일한 재귀 단계에서 중복된 숫자는 건너뛰기
                if candidates[i] == prev:
                    continue

                # Choose the current number
                # 현재 숫자를 선택
                subset.append(candidates[i])
                
                # Recur with the next index
                # 다음 인덱스로 이동하여 재귀 호출
                backtrack(subset, i + 1)
                
                # Backtrack: Remove the last chosen number
                # 백트래킹: 마지막으로 선택한 숫자를 제거하여 상태 복구
                subset.pop()
                
                # Update the previous number to the current number
                # 중복 제거를 위해 이전 숫자 갱신
                prev = candidates[i]

        # Start backtracking with an empty subset from the first index
        # 빈 부분집합과 첫 번째 인덱스부터 백트래킹 시작
        backtrack([], 0)
        
        # Return all unique combinations
        # 모든 고유한 조합 반환
        return res