dfs java

여기서 dfs함수는 방법의 수를 리턴

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

    private int dfs(int[] numbers, int target, int index, int currentSum) {
        // base case: 모든 숫자를 다 사용한 경우
        if (index == numbers.length) {
            // 현재 합이 타겟 넘버와 같으면 1을 반환 (방법의 수 1개 추가)
            return currentSum == target ? 1 : 0;
        }
        
        // 현재 숫자를 더한 경우와 뺀 경우를 각각 재귀적으로 탐색
        int add = dfs(numbers, target, index + 1, currentSum + numbers[index]);
        int subtract = dfs(numbers, target, index + 1, currentSum - numbers[index]);
        
        // 두 경우의 합이 현재 숫자를 처리한 결과
        return add + subtract;
    }

    public static void main(String[] args) {
        TargetNumber targetNumber = new TargetNumber();
        int[] numbers = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(targetNumber.solution(numbers, target)); // Output: 5
    }
}