[LeetCode] 40. Combination Sum II

백트레킹을 활용해야 하는 문제이다.

용이한 탐색을 위해 오름차 순으로 배열을 정렬한 후 target에서 현재 인덱스의 요소를 빼며 정확히 맞아 떨어지는 순간에 조합을 정답 배열에 추가한다.

중복 요소를 피하는 로직이 필요하며, 다음 백트레킹을 실행한 후 현재 조합을 빼 모든 경우의 수를 탐색한다.

😎풀이

function combinationSum2(candidates: number[], target: number): number[][] {
    const result = [];
    
    candidates.sort((a, b) => a - b);
    
    // 백트래킹 함수 정의
    const backtrack = (start: number, target: number, currentCombination: number[]) => {
        // 타겟이 0일 경우, 현재 조합을 결과에 추가
        if (target === 0) {
            result.push([...currentCombination]);
            return;
        }
        
        // 타겟이 0보다 작거나 시작 인덱스가 candidates 길이를 초과하면 종료
        if (target < 0 || start >= candidates.length) {
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            // 중복된 조합을 피하기 위해 이전 숫자와 같으면 건너뜀
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }
            
            // 현재 숫자를 조합에 추가
            currentCombination.push(candidates[i]);
            // 다음 숫자로 넘어가면서 타겟에서 현재 숫자를 뺀 값을 넘김
            backtrack(i + 1, target - candidates[i], currentCombination);
            // 마지막에 추가한 숫자를 제거하여 다음 조합을 위해 초기화
            currentCombination.pop();
        }
    };
    
    // 백트래킹 시작
    backtrack(0, target, []);
    return result;
}