[프로그래머스] 타겟 넘버 - DFS

문제 링크 : 타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

내 풀이 (DFS)

	int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers,0,target);
        return answer;
    }
    public void dfs(int[] numbers, int depth, int target){
        if(depth == numbers.length){
            if(target == 0){
                answer++;
            }
        } else{
            dfs(numbers, depth + 1, target + numbers[depth]);
            dfs(numbers, depth + 1, target - numbers[depth]);
        }
    }

dfs 함수는 숫자들의 배열 numbers, 현재 탐색할 배열의 index depth, 그리고 구해야 하는 타겟 넘버 target을 매개변수로 갖는다.
함수 내에서는 depth가 numbers의 원소의 갯수와 같아지면 target의 값을 검사하는데, target의 값이 0이면 정답의 갯수를 한개씩 늘린다.
만약 depth가 numbers의 원소의 갯수와 다르면 배열을 끝까지 탐색한 것이 아니므로, depth를 1씩 늘리고, target에서 현재 배열의 원소의 값을 각각 더하고 빼준 것을 인자로 하는 dfs 함수를 다시 호출한다.
그 후 solution 함수에서 answer를 반환한다.