[JAVA][Programmers] 타겟 넘버

프로그래머스

---

📌 접근 방식

주어진 숫자 배열에서 각 숫자에 대해 더하거나 빼는 두 가지 선택을 재귀적으로 탐색하여, 그 결과가 주어진 타겟 값과 일치하는 경우의 수를 구하는 문제입니다.

• dfs 함수는 배열의 끝에 도달할 때까지 각 숫자에 대해 더하거나 빼는 두 가지 경우를 재귀적으로 호출하며 탐색
• 배열의 끝에 도달하면, 현재까지의 합(sum)이 타겟 값(target)과 일치하면 정답 카운트(answer)를 증가

---

class Solution {
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }
    public void dfs(int[] numbers, int target, int idx, int sum) {
        if(idx == numbers.length){
            if(sum == target) {
                answer ++;
            }
            return;
        }
        dfs(numbers, target, idx+1, sum + numbers[idx]);
        dfs(numbers, target, idx+1, sum - numbers[idx]);
    }
}