PentaS

class Solution {
    int answer;

    public int solution(int[] numbers, int target) {
        answer = 0;
        dfs(numbers, target, 0, '+', 0);
        dfs(numbers, target, 0, '-', 0);

        return answer;
    }

    public void dfs(int[] numbers, int target, int sum, char ch, int idx) {
        switch (ch) {
            case '+':
                sum += numbers[idx];
                break;
            case '-':
                sum -= numbers[idx];
                break;
        }

        if (idx == (numbers.length - 1)) {
            if (sum == target) {
                answer++;
            }
        } else {
            dfs(numbers, target, sum, '+', idx + 1);
            dfs(numbers, target, sum, '-', idx + 1);
        }
    }
}

재귀함수를 이용한 DFS 알고리즘으로 접근을 했다.

DFS를 이용해야겠다는 생각은 했지만 stack을 이용한 DFS로 처음에 접근했다.

약간의 힌트를 통해 재귀함수로 방향을 바꾸었으나, dfs 메소드 반환형을 int로 해야한다는 강박에 return 조건을 어떻게 설정해야하나 고민했었다.

결국 다른 분의 코드를 참고하여 반환형을 void로 바꾸고 idx값 비교와 sum 값 비교를 통해 문제를 해결할 수 있었다.


핵심

1. 재귀함수 반환형 void
2. idx값이 배열 끝에 도달했을 때, sum이 target과 같은지 비교