[프로그래머스 DFS/BFS] 타겟 넘버 - JavaScript

문제 링크

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

코딩테스트 연습 - 타겟 넘버

풀이

function solution(numbers, target) {
    const dfs = (index, sum) => {
        if (index === numbers.length) {
            if (sum === target) {
                return 1;
            }
            return 0;
        } else {
            const plus = dfs(index + 1, sum + numbers[index]);
            const minus = dfs(index + 1, sum - numbers[index]);
            return plus + minus;
        }
    };
    return dfs(0, 0);
}

DFS로 numbers의 0번째 부터 마지막까지 모든 요소를 각각 덧셈 또는 뺄셈한 결과를 모두 확인하여 target과 같은 경우의 개수를 세어 해결할 수 있다.

 

DFS는 numbers의 길이만큼 재귀호출된 후(index가 numbers.length와 같을 때까지), sum이 target과 같으면 1을, 아니면 0을 반환한다. numbers의 길이만큼 호출되기 전에는 index를 1씩 증가시키며 index번 째 요소를 더한 경우와 뺀 경우를 각각 DFS로 재귀호출하여 두 값(plus, minus)을 더한 값을 반환한다.

 

이렇게 해서 모든 경우에 대해서 합이 target이 될 때마다 1씩 더하여 target을 만드는 방법의 개수를 구할 수 있다.