[프로그래머스/JavaScript] Lv.2 타겟넘버

 

해당 문제는 DFS문제로 경우의 수를 구하는 문제이다.

 

* BFS 사용 예
- 최단거리, 최소 횟수, 미로, 탐색 등

* DFS 사용 예
- 경우의 수, 이동 과정에 제약 있음 등

 

문제 
https://school.programmers.co.kr/learn/courses/30/lessons/43164

 

 

문제 풀이

let answer = 0
function solution(numbers, target) {
    // 1) DFS 함수 최초 실행 합(sum), 인덱스(idx) 0으로 셋팅
    dfsSum(0, numbers, 0, target);
    return answer;
}
function dfsSum(sum, numbers, idx, target) {

    // 2) 인덱스(idx)가 배열 길이와 같아지면 return한다.
    if(numbers.length === idx) {
        // 3) 합(sum)이 목표(target)값과 같아지면 answer 증가
        if(sum === target) return answer++;
        
        // 4) 다를 경우 그냥 return
        else return;
    }
    
    // 5) 더하는 DFS 함수
    dfsSum(sum+numbers[idx], numbers, idx+1, target);

    // 6) 빼는 DFS 함수
    dfsSum(sum-numbers[idx], numbers, idx+1, target);
    
    return answer;
}