문제

정답 풀이

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) {
                answer += sum==target ? 1 : 0;
            } else {
                dfs(numbers, target, depth+1, sum+numbers[depth]);
                dfs(numbers, target, depth+1, sum-numbers[depth]);
            }
    }
}

dfs문제이다.

풀이를 그림으로 확인해보면 쉽게 이해 할 수 있다.

검은색이 +, 하얀색이 - 라고 한다면

1. 해당 숫자를 더할 것인지, 혹은 뺄 것인지 선택한다.
2. 그 뒤에 다음 숫자를 더할 것인지, 혹은 뺄 것인지 선택한다.
3. 반복...

다음 숫자 나타내기 위해 depth라는 index를 사용한 것이며, 반복적인 선택을 위해 재귀 호출을 사용했다.

모든 탐색이 끝나면(depth==numbers.length), sum이 target과 일치하는지 확인한다.

다른 사람 풀이

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);
    }
}

이분도 재귀호출을 사용했는데, return 부분에 사용한 것이 인상적인다.