[JAVA] DFS(깊이우선탐색) : 타겟넘버

1. 문제 내용

요약
정수 배열이 입력되면 그 정수들이 +,-를 통해 target 값을 만들 수 있는 경우의 수를 반환하라

2. 접근방법
모든 경우를 탐색해야하고 +의 경우와 -의 경우가 나누어져 있는 것이 트리의 형태와 비슷한걸로 보인다
그러므로 트리의 모든 경우의 수를 찾기 위해 DFS를 사용해 보았다

3. 구현과정

class Solution {
    int count = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return count;
    }
    public void dfs(int[] numbers, int target, int index ,int total){
        if(index == numbers.length) {
            if(total == target) count++;
            return;
        }

        int sub = total - numbers[index];
        dfs(numbers, target, index+1, sub);

        int plus = total + numbers[index];
        dfs(numbers, target, index+1, plus);

    }
}

 배열의 첫번째부터 값을 +했을 경우와 -했을 경우를 재귀호출을 통해 구현했다
1,1,1,1,1이 들어오면
-1 -> -1 -> -1 -> -1 -> -1
-1 -> -1 -> -1 -> -1 -> +1
이런 순으로 제일 마지막으로 가서 -와 +를 하고 그과정이 점점 앞으로 오도록 했다

4. 결과