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

깊이 우선 탐색(DFS)으로 목표 값 찾기

이 문제는 주어진 정수 배열 numbers와 목표 값 target을 사용하여 배열의 각 요소를 더하거나 빼는 모든 가능한 방법을 탐색하여 목표 값과 일치하는 경우의 수를 찾는 문제입니다.

문제 풀이

이 문제를 해결하기 위해 DFS(깊이 우선 탐색) 방법을 사용했습니다. 각 숫자를 더하거나 빼는 두 가지 선택지를 재귀적으로 탐색하여 목표 값과 일치하는 경우를 찾습니다.

핵심 포인트

1. 재귀 함수 사용: 재귀 함수를 사용하여 모든 가능한 합계를 탐색합니다.
2. 기저 사례: 배열의 모든 숫자를 사용한 경우, 현재 합계가 목표 값과 일치하는지 확인합니다.
3. 재귀 호출: 각 숫자를 더하거나 뺀 두 가지 경우를 재귀적으로 탐색하여 결과를 합산합니다.

 

---

정답은 더보기 클릭

 

class Solution {
    public int solution(int[] numbers, int target) {
        // DFS 탐색을 시작합니다. 초기 호출에서는 인덱스 0과 합계 0을 사용합니다.
        return dfs(numbers, 0, 0, target);
    }

    public int dfs(int[] numbers, int index, int currentSum, int target) {
        // 모든 숫자를 다 사용한 경우
        if (index == numbers.length) {
            // 현재 합계가 목표 값과 일치하는지 확인
            return currentSum == target ? 1 : 0;
        }
        
        // 현재 인덱스의 숫자를 더하거나 빼는 두 가지 경우의 결과를 재귀적으로 계산하고 합산
        return dfs(numbers, index + 1, currentSum + numbers[index], target) 
             + dfs(numbers, index + 1, currentSum - numbers[index], target);
    }
}