[Javascript] 타겟 넘버 (43165)

문제링크

코딩테스트 연습 - 타겟 넘버

 

접근 방법

완전 탐색 문제로 dfs(깊이 우선 탐색) 방식으로 진행하였다.

주어진 배열이 [1,1,1,1,1] 일때
1, 1, 1, 1, 1
1, 1, 1, 1, -1
1, 1, 1, -1, 1
1, 1, 1, -1, -1
1, 1, -1, 1, 1
1, 1, -1, 1, -1
1, 1, -1, -1, 1
1, 1, -1, -1, -1
... 이런 방식의 트리 형태로 진행된다.

깊이 우선 탐색의 대표적인 기본 예제라고 할 수 있을만한 문제였다.

 

function solution(numbers, target) {
    let answer = 0;
    
    const dfs = (level, result) => {
        if(level === numbers.length){
            if(result === target) answer += 1;
            return;
        }
        
        dfs(level + 1, result + numbers[level])
        dfs(level + 1, result - numbers[level])
    }
    
    dfs(0,0);

    return answer;
}