프로그래머스 타겟넘버 js

프로그래머스 타겟넘버

---

배열에 나열된 숫자를 더하거나 빼면서 타겟넘버가 될 수 있는 경우의 수를 구하는 문제

모든 경우 (배열원소 하나하나에 덧셈 또는 마이너스를 해야함)의 수를 찾아야 하기 때문에 완전탐색, 그중에 dfs로 해결

dfs는 재귀로 구현하고 재귀이기에 base case를 넣어주어야한다.

여기서 base case, 재귀가 종료되는 조건은 연산횟수가 배열의 길이와 같을 때 종료한다.

경우의 수를 찾는 조건은 연산된 sum이 타겟넘버와 같을 때 answer를 1 증가시킨다.

백트래킹으로 덧셈 후, 마이너스 연산을 수행하도록 작성한다.

function solution(numbers, target) {
  var answer = 0;
  const dfs = (n, t, s, i) => {
    if (n.length <= i) {
      if (s === t) {
        answer++;
      }
      return;
    }
    dfs(n, t, s + n[i], i+1);
    dfs(n, t, s - n[i], i+1);
  };
  dfs(numbers, target, 0, 0);
  return answer;
}

console.log(solution([1, 1, 1, 1, 1]), 3);