타겟 넘버

문제

풀이

class Solution {
    static int answer=0;
    
    public static void DFS(int L,int sum,int[] numbers,int target){
        if(L==numbers.length){
            if(sum==target) answer++;
        }
        else{
            DFS(L+1,sum+numbers[L],numbers,target);
            DFS(L+1,sum-numbers[L],numbers,target);
        }
    }
    
    public int solution(int[] numbers, int target) {
        DFS(0,0,numbers,target);
        return answer;
    }
}

DFS문제이다. 문제를 잘 읽어야한다. 문제에서는 해당 numbers에 있는 요소들을 한번씩만 사용하고 +,-를 해줘서 target과 같은 수를 만드는 경우의 수를 return하라고 한다.
그래서 코드에서의 빽트래킹을 하는 부분을 해당 L이 numbers배열과 길이가 같으면서 sum이 target과 같을 때 answer++를 해준다.

재귀 호출부분에서 DFS()를 호출할 때 처음에는 한번씩 순서대로 쓰는 건 줄 모르고 for문으로 해줬다가 뭐지 싶었다. 문제를 잘 읽자.