(Java)프로그래머스 - 타겟 넘버

나의 풀이

class Solution {
    int answer = 0;

    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0); // 1

        return answer;
    }

    public void dfs(int[] numbers, int depth, int target, int sum){
        if(depth == numbers.length){ // 2
            if(target == sum) answer++;
        } else { // 3
            dfs(numbers, depth + 1, target, sum + numbers[depth]);
            dfs(numbers, depth + 1, target, sum - numbers[depth]);
        }
    }
}

과정

1. dfs메소드를 호출해 결과를 반환
2. depth가 numbers.length까지 탐색한 경우 target이 sum과 같으면 answer을 증가
3. depth가 numbers.length가 아니라면 해당 노드의 값을 더하고, 빼고 다음 노드 탐색

다른 사람 풀이

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = dfs(numbers, 0, 0, target);
        return answer;
    }
    int dfs(int[] numbers, int n, int sum, int target) {
        if(n == numbers.length) {
            if(sum == target) {
                return 1;
            }
            return 0;
        }
        return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
    }
}