프로그래머스 타겟 넘버 - level2(dfs)

오늘은 프로그래머스 타겟 넘버 문제를 풀어보겠습니다.

 

문제는 다음과 같습니다. 

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

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

 

* 풀이 방법

- 전형적인 완전탐색문제입니다. dfs를 이용해서 문제를 간단하게 풀 수 있습니다.

- 1과 -1로 만들 수 있는 모든 경우의 수를 찾고 개수를 누적 후 반환해주면 됩니다.

 

* 코드 

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