프로그래머스 Lv.2 | (DFS) 타겟 넘버 js

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

풀이

• 모든 가능한 조합을 시도해봐야 한다. numbers 배열의 숫자를 순서대로 + 혹은 -를 해봐야 한다. 마치 각 숫자 노드에 다음 숫자가 +, - 두 가지 버전으로 달려있는 이진트리를 모두 순회하는 경우와 같다.

1. 깊이 우선 탐색(DFS) 이므로 dfs라고 함수를 만들고, 다음 인덱스로 넘어가기 위한 index, 합을 축적할 currSum을 마련한다.
2. 인덱스와 sum은 0부터 시작하므로 처음에는 dfs(0, 0)로 시작한다.
3. dfs의 종료 조건은 index가 numbers.length가 될 때 (배열의 인덱스 범위보다 넘쳤을 때)이다. 이때는 여태가지 축적한 sum이 target과 같은지 검사하고, 맞다면 count++ 해준다.
4. dfs 재귀호출에서 인덱스 파라미터는 index + 1로 다음 인자를 호출하고, sum은 sum에 숫자를 더하거나 뺀 두 가지 버전을 준비한다.
5. dfs 호출이 모두 끝났으면 count를 반환한다.

function solution(numbers, target) {
    let count = 0;
    function dfs(index, currSum) {
        if(index === numbers.length) {
            if(currSum === target) count++;
            return;
        }
        
        dfs(index + 1, currSum + numbers[index]);
        dfs(index + 1, currSum - numbers[index]);
    }
    
    dfs(0, 0);
    return count;
}