[자바] 타겟넘버

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

프로그래머스

전형적인 깊이우선탐색 유형이다.

깊이를 우선으로 탐색하면서 모든 경우의 수를 조합해서 숫자를 만들어 내는 문제이다. 

 

depth가 끝까지 돌았고, sum과 target number가 같으면 answer+1하고, return;

만약끝까지 돌지 않았다면 +도 해보고 -도 하면서 숫자를 조합해본다. 

 

class Solution {
    public static 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) {
            if (sum==target) {
                answer++;
            }
            return;
        }
        dfs(numbers, target, depth+1, sum+numbers[depth]);
        dfs(numbers, target, depth+1, sum-numbers[depth]);

    }
}