[Programmers] 타겟 넘버

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

프로그래머스

문제 설명

간단한 완전 탐색 문제이다. DFS를 활용하여 해결했다. 현재 위치와 numbers의 길이가 같으면 모든 수에 대한 연산을 한 것이므로 그때의 합계를 타겟 넘버와 비교한다. 만약 같다면 1을, 아니라면 0을 반환하고 그 총합을 result에 담아 반환하면 된다.

코드

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    private int dfs(int[] numbers, int target, int sum, int current) {
        int result = 0;

        if (current == numbers.length) {
            return target == sum ? 1 : 0;
        }

        result += dfs(numbers, target, sum + numbers[current], current + 1);
        result += dfs(numbers, target, sum + numbers[current] * -1, current + 1);

        return result;
    }
}