Lv 2. 타겟 넘버

 

DFS 를 이용하여 Depth 만큼 파고 들면서 - , + 를 탐색하였다.

최종 Depth에 도착했을 시 target 과 결괏값을비교하여 answer 를 1씩 더하는 식으로 풀어내었다.

 

import java.util.*;

class Solution {
    public int answer = 0, end;
    public boolean[] isVisited;
    public int solution(int[] numbers, int target) {
        isVisited = new boolean[numbers.length];
        end = target;
        DFS(0,numbers,0);
        return answer;
    }
    public void DFS(int depth, int[] numbers, int num){
        if(depth == numbers.length){
            if(end == num)
                answer++;
            return;
        }
        isVisited[depth]=true;
        DFS(depth+1,numbers,num+numbers[depth]);
        DFS(depth+1,numbers,num-numbers[depth]);
        isVisited[depth]=false;
    }
}