[LeetCode] 39. Combination Sum

DFS를 활용하여 가능한 경우의 수를 구하면 된다.

다만 다른 조합 문제와는 다르게 중복 선택이 가능하므로

해당 인덱스의 요소를 선택할 경우 다음 요소로 넘어가지 않고 다시 체크하는것이 중요하다.

😎풀이

function combinationSum(candidates: number[], target: number): number[][] {
    // 결과를 저장할 배열
    const result = [];
    
    // 깊이 우선 탐색(DFS) 함수 정의
    function dfs(index: number, current: number[], sum: number) {
        // 목표값에 도달했을 경우, 현재 조합을 결과에 추가
        if (sum === target) {
            result.push([...current]);
            return;
        }
        
        // 목표값을 초과하거나 모든 후보를 검사했을 경우 종료
        if (sum > target || index >= candidates.length) {
            return;
        }
        
        // 현재 숫자를 포함하는 경우 (중복 사용이 가능하므로 index는 +1 하지 않음)
        current.push(candidates[index]);
        dfs(index, current, sum + candidates[index]);
        
        // 현재 숫자를 포함하지 않는 경우 (백트래킹)
        current.pop();
        dfs(index + 1, current, sum);
    }
    
    // DFS 탐색 시작
    dfs(0, [], 0);
    
    return result;
}