[JAVA] Lv.2 타겟 넘버 - 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

import java.util.*;
class Solution {
    static int[] pm;
    static int tn, answer = 0;
    public int solution(int[] numbers, int target) {
        pm = numbers.clone();
        tn = target;
        dfs(0, 0);
        return answer;
    }
    public void dfs(int idx, int acc){
        if(idx == pm.length){
            if(acc == tn) answer++;
            return;
        }
        dfs(idx+1, acc+pm[idx]);
        dfs(idx+1, acc-pm[idx]);
    }
}

- 가능한 경우에 대해 모두 탐색해 개수를 구해야 하므로, DFS 활용

- 분기를 idx에 해당하는 수를 더하냐/빼냐로 두고 진행함

• 다른 풀이를 참고하니, dfs를 애초에 target값에 달성하면 1을 반환하게 해서 -> 최종적으로 return에서 누적돼서 반환하게함

import java.util.*;
class Solution {
    public int solution(int[] numbers, int target) {
        dfs(0, 0);
        int answer = dfs(0, 0, numbers, tartget);
        return answer;
    }
    int dfs(int idx, int acc, int[] numbers, int target){
        if(idx == numbers.length){
            if(acc == target) return 1;
            return 0;
        }
        return dfs(idx+1, acc+numbers[idx], numbers, tartget) + dfs(idx+1, acc-numbers[idx], numbers, tartget)
    }
}