타겟 넘버

문제

---

문제 풀이

문제자체는 그렇게 어렵지 않은 문제이긴 했으나, dfs를 구현하는 방법을 어떻게 할 지에 대한 고민을 많이 했던 문제이다. 

 

배열로 받은 값을 +로 더해보고 -로 빼야하는 모든 경우의 수를 생각해봐야 하기 때문에 재귀함수로 +, - 값을 계산하도록 해야 한다. 

 

그리고 idx 가 배열의 끝까지 도달 했을 때, 그 때의 합이 target과 같다면 answer + 1 해주면 된다. 

---

나의 답안

class Solution {
    static int answer = 0;

    public int solution(int[] numbers, int target) {

        dfs(numbers, target, 0, 0);

        return answer;
    }

    private void dfs(int[] numbers, int target, int idx, int sum) {
        if (idx == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        dfs(numbers, target, idx + 1, sum + numbers[idx]);
        dfs(numbers, target, idx + 1, sum - numbers[idx]);

    }
}