고득점 Kit [DFS/BFS] - 타겟넘버

문제

풀이

전형적인 DFS 문제, 모든 숫자가 (+)인 경우를 탐색한 후 다음 인덱스가 (-)인 경우를 탐색, 더하는 dfs가 먼저 있기 때문이다.

여기서의 핵심은 count+1의 값을 전달 해준 것
우리는 dfs(count, sum)에서 dfs(0, 0)을 전달 했으므로 dfs의 재귀는 1~5에서만 계속하여 재귀한다.

+로 5개를 채웠을 때 찾지 못했다면 index 4로 넘어와서 -를 한 개 넣준다

★★ 여기에서의 핵심과 가장 헷갈릴 수 있는 방법은 -를 넣어서 target값과 일치한다면 dfs전체를 빠져나가는 것이 아니라

return을 만나 다시 dfs의 더하기를 실행한다는 것
즉, 5에서 답을 찾고 다시 0으로 가는 것이 아니라 그림처럼 다시 4로 돌아가서 더하기부터 다시 함

function solution(numbers, target) {
    let ans = 0;
    
    function dfs(count, sum) {
        console.log(count, sum)
        
        if (count === numbers.length) {
            if (target === sum) {
                ans++
            }
            return // ★ return에서 끝난 후로 다시 dfs의 더하기부터 시작 ★
        }
        // 맨 처음에 위에 있는 더하기 dfs가 먼저 쭉 실행 (count가 5가 될 때까지)
        dfs(count+1, sum + numbers[count])
        // 그러다가 더하기 5번으로 되지 않는다면 더하기 dfs 4번 + 빼기 dfs 1번으로 
        dfs(count+1, sum - numbers[count])
    }
    
    dfs(0, 0)
    
    return ans
    
}