프로그래머스 #Javascript - 타겟넘버

문제

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

풀이

function solution(numbers, target) {
    var answer = 0;

// 원래 내가 생각한 방법
// 1.+,- 로 가능한 모든 조합을 담은 배열을 만들고
// 2.그 배열과 숫자배열을 이용해서 반복문을 통해 계산해서
// 3.타겟넘버가 나오면 answer ++해주기
// 1번 배열을 어떻게 만들어야 하는지??

// (참고) DFS 알고리즘 이용 - 재귀
    function recur(index, sum){
      // leaf node 도착했을 때, 모든 numbers 탐색
        if( index === numbers.length){
            if(sum === target ){
                answer+=1;
            }
            return;
        }
        // left child가 +일 경우
        recur(index+1, sum+numbers[index]);
       // right child가 -일 경우
        recur(index+1, sum-numbers[index]);
    }
    
    recur(0, 0); //초기값
    
    return answer;
}

더 생각해보기

참고사항

#DFS 깊이우선탐색