[pro] 프로그래머스 level2 43165 타겟 넘버 (Java) - DFS

[문제]

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

프로그래머스

 

[풀이]

단순한 dfs 문제.

numbers 배열 숫자에 대해서 + 또는 - 두 가지 경우가 존재한다.

 

[코드]

 

class Solution {
    int ans;
    public int solution(int[] numbers, int target) {
        int answer = 0;
        //숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return
        
        dfs(0, numbers, 0, target);
        
        answer = ans;
        
        return answer;
    }
    
    public void dfs(int depth, int[] numbers, int now, int target){
        if(depth==numbers.length){
            if(now==target) ans++;
            return;
        }
        
        dfs(depth+1, numbers, now+numbers[depth], target);
        dfs(depth+1, numbers, now-numbers[depth], target);
        
        return;
    }
}