[프로그래머스 레벨2] 타켓 넘버 [Javascript/ DFS]

문제 유형

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

프로그래머스

 

문제 풀이

+, - 선택 (있거나 없거나) 
양자 택일은 dfs
또한, 연산 끝이(depth) 있다. (피연산자 개수만큼)

기저조건을 피연산자를 다 사용했을 때와 count 개수 세는 로직과 분리해야 한다. 

만약   if(count === numbers.length && sum === target) 이렇게 설계하면 함수 종료 return과 count 둘 중 하나가 안 돌아간다. (무한 호출 dfs)

 

 

전체 코드

function solution(numbers, target) {
   function dfs(count, sum) {
      // 피연산자를 다 사용했으면
     if(count === numbers.length){
      // 총합이 targer 하고 같은지 확인
       if(sum === target) answer++;
        return;
     }  
       let num = numbers[count]
       dfs(count+1,sum+num)
       dfs(count+1,sum-num)
   }  
    let answer = 0;  // function 안에 function 선언하면 전역변수로 사용가능  
    dfs(0,0)
    return answer;  
}