[프로그래머스/Java] 타겟 넘버 (DFS)

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java

프로그래머스

1. 기저 조건 (탈출 조건)

- 숫자를 다 골랐을 때( index == numbers.length ) 바닥에 도착한 것

- 이때 sum == target 이라면 정답 카운트 올린다

 

2. 재귀 단계 (갈래길 탐색)

- 현재 숫자를 더하는 경우 : dfs(index+1, sum+현재숫자)

- 현재 숫자를 빼는 경우 : dfs(index+1, sum-현재숫자)

class Solution {
    int answer = 0;
    public int solution(int[] numbers, int target) {
        // 0번째 인덱스부터, 시작 총합은 0부터 탐색 시작
        dfs(numbers, target, 0, 0);
        return answer;
    }
    
    public void dfs(int[] numbers, int target, int index, int sum){
        // 기저조건 : 모든 숫자를 다 사용해서 바닥에 도달
        if(index == numbers.length){
            // 지금까지의 총합이 타겟넘버와 같다면 정답 카운트 증가
            if(sum == target){
                answer++;
            }
            return;
        }
        
        // 재귀 단계 : 현재 숫자를 더하거나 빼는 두 갈래길 탐색
        dfs(numbers, target, index+1, sum+numbers[index]); // 더하기 선택
        dfs(numbers, target, index+1, sum-numbers[index]); // 빼기 선택
    }
}