[고득점kit/깊이/너비 우선 탐색] 타겟 넘버

비교적 쉽게 풀 수 있었다! 사실 처음엔 주어진 수를 다 더해서 sum - target을 한 다음에 나온 값을 만들어 보는 방식으로 해볼까 했는데 당연히 쓸데 없는 단계가 한번 더 추가 되면 비효율적이죠?

class Solution {
    int answer = 0; 
    public int solution(int[] numbers, int target) {
        //재귀 호출
        dfs(numbers, target, 0, 0);
        return answer;
    }
    
    public void dfs(int[] numbers, int target, int depth, int sum){
        if(depth == numbers.length){
            if(sum == target) answer++;
        }else{            
        dfs(numbers, target, depth+1, sum+numbers[depth]);
        dfs(numbers, target, depth+1, sum-numbers[depth]);
        }
    }
}

다음에 탐색하는 노드를 더하거나 빼며 가는 방식으로 모든 경우를 구하게 만들었다

1

1 + 1 / 1 - 1

1 + 1 + 1 / 1 + 1 - 1/ 1 - 1 + 1 / 1 - 1 - 1

... 이런식으로! 더하거나? 빼거나!