[Algorithm] 타겟넘버

문제설명

타겟넘버는 정수 배열과 타겟이 되는 정수를 인자로 받아 정수 배열의 요소를 모두 사용하여 타겟 정수를 만들 수 있는 경우의 수를 구하는 문제이다. 정수 배열의 모든 요소에 순서를 변경하면 안되고 적절히 더하거나 빼서 타겟 정수를 완성해야 한다.

문제해결

모두 사용해야 한다 -> 모든 요소를 조회해야 한다.

덧셈 뺄셈이 가능하다 -> 모든 요소를 조회하며 더해보고 빼봐야 한다.

function solution(numbers, target) {
    let answer = 0;
    
    function dfs (idx, num) {
        // 모든 요소를 조회한 뒤
        if (idx === numbers.length) {
          // 구한 값과 타겟이 일치하면 경우의 수 추가
          if (num === target) answer++;
          return;
        }
        // 재귀를 호출하여 다음 인덱스로 넘어가며 더하고 빼는 모든 경우의 수를 구한다.
        dfs(idx + 1, num + numbers[idx]);
        dfs(idx + 1, num - numbers[idx])
    }
    // 초기값 0번째 인덱스부터 
    dfs(0,0)
    
    return answer;
}