[Algorithm] Programmers_타겟넘버

[문제 링크]
https://programmers.co.kr/learn/courses/30/lessons/43165?language=javascript#

function solution(numbers, target) {
    var answer = 0;
    
    //numbers 배열의 모든 총 합이 target과 같은 경우 다른 방법은 없으므로 1로 리턴
    if (numbers.reduce((pre, cur) => pre + cur) === target) return 1;
    
    //재귀 작성
    const dfs = (cnt, sum) => {
    	//전체 배열의 길이보다 작은 경우에만
        if (cnt < numbers.length) {
        	//더했을 경우와 뺏을 경우 모두 비교해야하므로
            dfs(cnt + 1, sum + numbers[cnt])
            dfs(cnt + 1, sum - numbers[cnt])
        } else {
        	//모든 numbers를 다 순회 한 이후 sum과 target이 같으면 ++
            if (sum === target) ++answer;
        }
    }
    
    dfs(0, 0)
    
    return answer;
}