프로그래머스 DFS/BFS 타겟넘버

DFS 문제의 형태로 재귀함수로 푸는 것이 특징인 것 같다. 다른 해설은 정답만 올려놔서 이해를 못했다. 직접 적어서 나중에 봐야겠다.

class Solution {
	static int answer; // 전역으로 뺴주기(이유는 solution, dfs에서 전부 사용)
    
    public int solution(int[] numbers, int target) {
    	answer = 0; // 1
        dfs(numbers, target, 0, 0); // 2
        return answer;
    }
    
    // 3 (numbers, target, idx: 몇 번째 인덱스 인지, sum: idx까지 누적합)
    public void dfs(int[] numbers, int target, int idx, int sum) {
    	if (idx == numbers.length) { // 4 모든 정수를 탐색했을 때
        	if (sum == target) answer++; // 5 누적합이 동일하면 증가 후 종료
            return;
        }
        
        sum += numbers[idx]; // 6 현재 인덱스의 정수를 +로 합치기
        dfs(numbers, target, idx + 1, sum); // 7 dfs 수행
        sum -= numbers[idx]; // 8 6의 값을 다시 빼기
        sum += (-1 * numbers[idx]); // 9 현재 인덱스의 정수를 -로 합치기
        dfs(numbers, target, idx + 1, sum); // 10 dfs 수행
    }
}