[프로그래머스 Level 2] 타겟 넘버 - 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;
        }
        const plus = dfs(index + 1, sum + numbers[index]);
        const minus = dfs(index + 1, sum - numbers[index]);
        return plus + minus;
    };
    return dfs(0, 0);
}

dfs를 정수의 개수만큼 재귀호출하여 각각의 인덱스의 수를 더했을 때와 뺐을 때의 모든 경우를 탐색한다.

 

마지막 인덱스까지 재귀호출했을 때, 지금까지의 합계(sum)가 목표한 값(target)과 같다면 1을, 같지 않다면 0을 반환한다.

마지막 인덱스가 아닐 때에는 인덱스를 1 증가시키고 현재 인덱스의 숫자를 더한 값을 인자로 넣어 재귀호출한 plus와 뺀 값을 인자로 넣어 재귀호출한 minus를 구하고, 그 둘을 더하여 반환한다.

 

목표한 값과 같을 때마다 base case에서 1을 반환하기 때문에, plus와 minus의 합은 현재 인덱스부터 마지막까지의 숫자로 만들 수 있는 모든 경우 중에 목표한 값을 만드는 경우의 개수가 된다.