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

---

📄 문제

타겟 넘버

 

💡 풀이

깊이 우선 탐색 (DFS)을 활용하여 주어진 숫자 배열에서 각 숫자를 더하거나 빼서 특정 목표 숫자(target)를 만들 수 있는 경우의 수를 계산하는 방식입니다.

 

class Solution {

    private int answer = 0;

    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }

    private void dfs(int[] numbers, int target, int index, int currentSum) {
        if (index == numbers.length) {
            // 배열의 끝까지 도달한 경우, 현재 합이 타겟과 일치하는지 확인하고 answer를 업데이트
            if (currentSum == target) {
                answer++;
            }
            return;
        }

        // 현재 숫자를 더하거나 빼서 모든 가능한 경우를 탐색
        dfs(numbers, target, index + 1, currentSum + numbers[index]);
        dfs(numbers, target, index + 1, currentSum - numbers[index]);
    }
}