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

    private int dfs(int[] numbers, int target, int index, int sum) {
        if (index == numbers.length) {
            return sum == target ? 1 : 0;
        }
        return dfs(numbers, target, index + 1, sum + numbers[index]) +
               dfs(numbers, target, index + 1, sum - numbers[index]);
    }
}

Approaches

이 문제는 각 숫자에 대해 더하거나 빼는 두 가지 선택을 반복하여 모든 가능한 조합을 탐색하는 방식으로 해결할 수 있습니다. 이를 위해 재귀적 접근 방식을 사용하여 깊이 우선 탐색(DFS)을 수행합니다. 다음은 구체적인 접근 방식입니다:

DFS를 이용한 탐색:
- 주어진 배열 numbers와 목표 값 target, 현재 인덱스 index, 현재 합계 sum을 인자로 받아 재귀적으로 탐색합니다.
- 해당 index의 각 숫자에 대해 sum에 덧셈 또는 뺄셈 두 가지 선택을 고려하여 다음 단계로 넘어갑니다.
- 예를 들어, 첫 번째 숫자에 대해 더하기와 빼기를 각각 선택하여 두 가지 경로로 재귀 호출합니다. 이후 두 번째 숫자에 대해 동일한 선택을 반복합니다.
- 이렇게 하나는 더하기 경우, 하나는 빼는 경우를 계속 재귀 호출하다 보면 모든 경우의 수가 탐색됩니다.
- 탐색 깊이가 배열의 길이에 다다랐을 때, 현재 합계가 목표 값과 일치하면 1을 반환하고, 그렇지 않으면 0을 반환합니다.
- 각 단계에서 두 가지 선택의 결과를 합산하여 최종적으로 가능한 모든 경우의 수를 계산합니다.

예를 들어, numbers = [4, 1, 2, 1]이고 target = 4인 경우 다음과 같이 DFS 탐색의 단계별로 진행됩니다:

이 다이어그램은 배열 [4, 1, 2, 1]을 사용하여 깊이 우선 탐색(DFS)을 통해 가능한 모든 경우의 수를 보여줍니다.

각 노드는 현재까지의 합계를 나타내며, 다음 단계에서 두 가지 선택을 통해 새로운 합계를 계산합니다.
최종 깊이(여기서는 4)에서는 모든 가능한 경우의 수를 탐색합니다.
각 경로가 목표 값(target)과 일치하는지 확인하고, 일치하면 해당 경로를 결과에 포함시킵니다.

이 방식은 DFS를 사용하여 모든 가능한 조합을 탐색하며, 최종적으로 목표 값과 일치하는 경우의 수를 합산하여 반환합니다. 모든 가능한 경우를 탐색하므로, 시간 복잡도는 O(2^n)이 됩니다. 배열의 크기가 최대 20이므로, 이 방식은 효율적입니다. 또한, 공간 복잡도는 재귀 호출의 깊이에 비례하여 O(n)이 됩니다.

Algorithm
DFS