문제 링크

바로가기

문제 풀이

let answer = 0;

function dfs(numbers, target, sum, cnt) {
    if(numbers.length === cnt) {
        if(sum === target) answer++;
        return;
    }else {
        dfs(numbers, target, sum + numbers[cnt], cnt + 1);
        dfs(numbers, target, sum - numbers[cnt], cnt + 1);
    }
}

function solution(numbers, target) {
    dfs(numbers, target, 0, 0);
    return answer;
}

새롭게 배운 점

오랜만에 코딩테스트를 봐야하는 일이 생겨서 다시 DFS/BFS를 공부중이다..
핵심은 재귀함수로 할 수 있는 경우의 수를 다 검사하는 법이다.

더하는 수와 빼는 수가 있기 때문에 깊이 우선 탐색을 통해 0부터 시작해서 수를 더하는 방법과 빼는 방법의 경우의 수를 하나하나 들어가면서 배열의 길이와 함수의 카운트 수가 같아 졌을 때 타겟 넘버가 일치하면 답을 하나 올려주는 형식으로 구현하였다.