[LeetCode 75] Medium - 216. Combination Sum III

216. Combination Sum III

 

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:        
        def backtrack(start, path, target):
            """
            백트래킹 함수
            :param start: 탐색을 시작할 숫자
            :param path: 현재까지 선택된 숫자의 리스트
            :param target: 남은 목표 합
            """
            # 1. base case: 조건을 만족하는 경우 결과에 추가
            if len(path) == k and target == 0:
                res.append(list(path))  # 경로를 결과에 추가
                return
            
            # 2. 숫자 탐색 (1~9)
            for i in range(start, 10):  # 시작 숫자부터 9까지
                # 2.1 현재 숫자가 목표 합을 초과하면 중단
                if i > target:
                    break
                
                # 2.2 숫자를 추가하고 백트래킹
                backtrack(i + 1, path + [i], target - i)

        # 결과 리스트 초기화
        res = []

        # 백트래킹 시작
        backtrack(1, [], n)

        # 결과 반환
        return res

 

특징

• 백트래킹의 핵심:
  • 현재 숫자가 목표 합을 초과하면 더 이상 탐색하지 않음 → 가지치기(Pruning).
  • 조합이 완성되면 결과에 추가.
• 효율적 탐색:
  • 숫자는 오름차순으로 탐색하며, 중복 조합을 방지.
• for i in range(start, 10):에서 start를 사용하는 이유는 중복된 조합을 방지하기 위해서입니다.
  • 만약 range(1, 10)으로 계속 1부터 다시 시작하면, 동일한 숫자 조합이 여러 번 생성될 수 있습니다.
  • 이 코드에서는 숫자를 오름차순으로 선택하므로,
  • 이미 탐색한 숫자는 다시 탐색하지 않도록 start를 활용합니다.

이 코드는 111부터 999까지의 숫자를 조합하여 목표 합을 효율적으로 찾습니다. 😊