Backtracking 기반의 Pick/Not Pick 전략을 통한 Target Sum 조합 최적화

Context

중복 선택이 가능한 정수 배열에서 특정 합계(Target)를 만드는 모든 유일한 조합을 생성해야 하는 과제. 단순 Brute Force 방식으로는 탐색 공간이 기하급수적으로 증가하여 비효율적인 경로 탐색이 발생하는 한계 존재.

Technical Solution

• Backtracking 기법을 적용하여 유효하지 않은 경로를 조기에 차단하는 Pruning 전략 수립
• Pick/Not Pick 결정 트리를 구축하여 모든 가능한 조합을 체계적으로 탐색하는 구조 설계
• 요소 선택 시 index를 유지하는 설계를 통해 동일 요소의 무제한 재사용 가능성 확보
• Target 값이 0이 되는 시점을 Base Case로 설정하여 유효 조합을 확정하는 재귀 로직 구현
• Target 값이 음수로 전환되는 즉시 탐색을 중단하여 불필요한 연산을 제거하는 효율성 확보
• DFS 기반의 상태 공간 트리 탐색 후 Stack에서 요소를 제거하는 Backtrack 과정을 통한 메모리 효율화