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

 

 

문제 설명

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

프로그래머스

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

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

 

 

문제 풀이

깊이 우선 탐색(DFS)를 사용해서 가능한 경우의 모든 수를 탐색하고, target 넘버를 만들 수 있는 경우의수를 찾기

재귀적으로 함수를 호출해서 호출할 때마다 index를 증가시켜 배열의 다음 원소를 탐색하기

function solution(numbers, target) {
    var answer = 0; // target을 만들 수 있는 경우의 수
    
    // 깊이 우선 탐색하기(배열 인덱스, 누적 합)
    function dfs(index, sum) {
        // 인덱스가 배열 끝(number.length)까지 탐색했으면 실행
        if(index === numbers.length) {
            // 누적합이 target과 같다면 answer 경우의 수 증가
            if(sum === target) {
                answer++
            }
            return
        }
        
        // 배열끝에 도달하지 않았을 경우
        // 재귀 호출 (인덱스 1씩 증가시키기, 현재 숫자를 더한경우와 뺀 경우를 호출)
        dfs(index + 1, sum + numbers[index])
        dfs(index + 1, sum - numbers[index])
    }
    
    dfs(0, 0); // 0부터 깊이 우선 탐색 시작
    return answer;
    
}