[프로그래머스] 타겟 넘버 / Javascript

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

풀이 과정

간단하게 재귀를 이용해서 풀면 된다.
정수를 하나 하나 확인하면서 현재까지의 결과값에 현재 정수를 더하거나 뺀 값과
현재 정수의 다음 인덱스를 함수의 매개변수로 넘겨준다.
모든 정수를 확인한 뒤에 타겟 넘버가 만들어졌다면
경우의 수를 1 증가시키는 형태로 코드를 작성하면 된다.

const solution = (numbers, target) => {
    const length = numbers.length;
    let cnt = 0;

    const dfs = (currentNumber, index) => {
        // 정수를 모두 확인했고
        if(index === length) {
            // 타겟 넘버가 만들어졌다면 cnt 1 증가
            if(target === currentNumber) {
                cnt++;
            }
            return;
        }
        // 정수를 더할 경우
        dfs(currentNumber + numbers[index], index + 1);
        // 정수를 뺄 경우
        dfs(currentNumber - numbers[index], index + 1);
    }

    dfs(0, 0)

    return cnt;
}