[JavaScript] 프로그래머스 - 타겟 넘버

[문제]

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

프로그래머스

 

[풀이]

대표적인 DFS 문제로 두가지 방향으로 이동이 가능합니다.

 

• + 연산을 해주고 다음 index로 이동
• - 연산을 해주고 다음 index로 이동

 

현재 계산중인 numbers의 index를 dfs 함수에 인수로 전달해 만약 모든 숫자가 연산이 완료되면, 즉 index가 numbers.length와 같아지면 dfs 함수를 return 합니다.

 

예시 1번의 과정을 살펴보면 아래와 같이 연산이 진행됩니다.

 

                               [1 + 1 , 1 - 1]

         [1 + 1 + 1, 1 + 1 - 1]   [1 - 1 + 1, 1 - 1 - 1]

                                        ...

 

[코드]

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