코테 DFS 2022.11.24

🙉 타겟 넘버 풀이

오늘 하루 종일 걸려 하나 한문제 이해 완료 했다 ^..^..

타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다. 
이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 
예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 
타겟 넘버 target이 매개변수로 주어질 때 
자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록
solution 함수를 작성해주세요.

입출력 예

numbers	target	return
[1,1,1,1,1]	3	5
[4,1,2,1]	4	2

예제

+4+1-2+1 = 4
+4-1+2-1 = 4

🎨풀이

코드 출처

function solution(numbers, target) {
  let answer = 0;
  const depth = numbers.length;

  function dfs(count, sum) {
    if (count === depth) {
      if (target === sum) {
        answer++;
      }
      return;
    }

    dfs(count + 1, sum + numbers[count]);
    dfs(count + 1, sum - numbers[count]);
  }

  dfs(0, 0);

  return answer;
}

DFS
노드마다 가장 깊이 탐색한 후에 다음 노드로 이동한다.

그림으로 구조를 그려보았다.

depth 는 입력 numbers[] 배열의 길이이다.
시작 노드부터 -4, 4 ... 트리를 그리면 이러한 형태이다.
DFS는 가장 깊이 탐색 후에 다음 노드로 이동하기 때문에 -4 -1 -2 -1 을 간 후 sum 값이 -8 이므로 저장하지 않고 return 으로 함수를 종료했다.

해당 노드를 빠져나와 다음 노드를 탐색하고
sum 값이 -6 이기에 return

target은 4이고
계속해서 실행하다보면 sum 값이 4가 되는 노드가 나온다. 그러면 그 값을 answer에 저장한다.

디버깅으로 확인해보기