[프로그래머스 / lv 2] 타겟 넘버 (JAVA)

문제

---

풀이방법

• 깊이 우선 탐색 알고리즘 사용
• 마지막 노드까지 탐색했을 때 타겟 넘버와 합계가 같으면 정답 카운트 증가
  • 탐색할 노드가 남아있는 경우, 이전 노드까지의 합에서 해당 노드의 값을 더하고 빼는 두가지 경우로 깊이 우선 탐색 알고리즘 재실행

---

코드

class Solution {
    int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers,0,target,0);
        return answer;
    }
    public void dfs(int[] numbers, int depth, int target, int sum){
        if(depth==numbers.length){
            if(sum==target){
                answer++;
            }
        }else{
            dfs(numbers,depth+1,target,sum+numbers[depth]);
            dfs(numbers,depth+1,target,sum-numbers[depth]);
        }
    }
}