[알고리즘 JS] 타겟 넘버 (프로그래머스 Lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

풀이

function solution(numbers, target) {
  let count = 0;
  const DFS = (level, sum) => {
    // 종료 조건
    if (level === numbers.length) {
      if (sum === target) count++;
      return;
    }
    // 반복 조건
    else {
      DFS(level + 1, sum + numbers[level]);
      DFS(level + 1, sum - numbers[level]);
    }
  };

  // level 로 numbers 에 접근하기 때문에 0부터 시작하는게 좋겠다
  DFS(0, 0);

  return count;
}

• DFS 방식을 알면 간단하게 풀 수 있는 문제. 근데 문제를 보자마자 이게 DFS 라는게 바로 생각나지 않았다. 같은 유형의 문제를 많이 접하는 연습이 필요할듯.
• 주어진 숫자 배열 전부를 사용하면서 더하고 빼서 타겟 넘버가 되는 경우의 수를 구하는 문제이다.
• 각 노드에 취할 수 있는 행동은 더하기, 빼기이기 때문에 number 의 길이만큼 깊이 우선 탐색을 하면서 각 노드가 더해지는 경우와 빠지는 경우를 구해 최종적인 값이 target 값이 되느냐를 판단하면 된다.