[프로그래머스_lv2] 타겟 넘버 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=javascript

프로그래머스

 

[유형]

- 깊이/너비 우선 탐색 (DFS/BFS)

 

 

 

 

[풀이]

💡 노드그래프 시각화할 수 있는 사이트:   https://csacademy.com/app/graph_editor/

 

 

dfs 풀이

const numbers = [4, 1, 2, 1]; //[1, 1, 1, 1, 1];
const target = 4; //3;

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

  function dfs(index, sum) {
    if (index < length) {
      dfs(index + 1, sum + numbers[index]);
      dfs(index + 1, sum - numbers[index]);
    } else {
      if (sum === target) answer++;
    }
  }
  console.log('Here!🌈', answer);
  return answer;
}

solution(numbers, target);

 

index === node 

처음엔 노드탐색을 0부터 할 것이니 index, sum 둘 다 0으로 시작

numbers 배열의 길이만큼만 탐색하면 되니까(조건문을 주고), 자식노드만 탐색하면 된다(재귀로)

+,- 연산 2가지가 있기 때문에 각각의 함수 2번 호출함