프로그래머스 - 타겟넘버 - 자바 - 코딩테스트연습

class Solution {
    int answer = 0; // 목표값과 일치하는 경우의 수를 저장할 변수

    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0); // 깊이 우선 탐색(DFS) 함수 호출

        return answer; // 결과 반환
    }

    // 깊이 우선 탐색 함수
    public void dfs(int[] numbers, int depth, int target, int sum){
        if(depth == numbers.length){ // 배열의 모든 요소를 다 탐색한 경우
            if(target == sum) answer++; // 목표값과 일치하는 경우 answer 변수 증가
        } else {
            dfs(numbers, depth + 1, target, sum + numbers[depth]); // 현재 인덱스의 값을 더하여 재귀 호출
            dfs(numbers, depth + 1, target, sum - numbers[depth]); // 현재 인덱스의 값을 빼서 재귀 호출
        }
    }
}

1. solution() 함수에서 dfs() 함수를 호출

2. dfs() 함수에서는 재귀적으로 자신을 호출

3. depth와 sum 값을 조정하여 모든 경우를 탐색

4. depth는 현재 탐색 중인 인덱스를 의미, sum은 현재까지의 누적값을 의미.
5. numbers 배열의 길이에 도달시

6. 현재까지의 누적값과 target이 일치하는지 확인

7. 일치하면 answer 값을 1 증가

모든 숫자 조합을 구해서 target과 일치하는 조합의 수를 구하는 문제를 DFS 알고리즘을 이용하여 해결하는 방법