문제

https://programmers.co.kr/learn/courses/30/lessons/43165
numbers의 숫자를 더하고 빼서 target숫자가 되는 경우의수가 몇개인지 구하는 문제

입력: [numbers, target]

• numbers: 2이상 20이하의 배열
  • 각 요소는 1이상 50이하인 자연수
• target: 1이상 1000 이하인 자연수

출력: 경우의수가 몇개인지 출력

문제풀이

dfs를 사용해 간단하게 풀었다.
모든 배열이 +, - 둘중의 하나의 경우가 있으므로
dfs 함수에서 해당 경우에 대해 재귀적으로 함수를 호출해 주었고
더한값이 target이 되거나 i가 numbers.length에 도달하면 return하게 해주었다.

function solution(numbers, target) {
    let result = 0;

    function dfs(sum, i) {
        if (i < numbers.length) {
            dfs(sum + numbers[i], i+1);
            dfs(sum - numbers[i], i+1);
        }else {
            if (sum === target) {
                result++;
            }
        }
    }
    dfs(0, 0);
    return result;
}