[프로그래머스/Java] 타겟 넘버

문제풀이 방법

DFS 사용
타겟 넘버를 만들 수 있는 경우의 수는 수를 더하거니 빼거나 2가지
-> 2가지 모두 실행시키면서 target과 같아지는 경우 answer++

💡 [1, 1, 1, 1, 1] → 3이 되는 경우

• depth = 0, sum = 0에서 시작
• dfs(numbers, 1, target, 1) 호출 (sum = 0 + 1)
  • dfs(numbers, 2, target, 2) 호출 (sum = 1 + 1)
    • dfs(numbers, 3, target, 3) 호출 (sum = 2 + 1)
      • dfs(numbers, 4, target, 4) 호출 (sum = 3 + 1)
        • dfs(numbers, 5, target, 5) 호출 (sum = 4 + 1) -> depth == numbers.length이므로 종료
          
        • dfs(numbers, 5, target, 3) 호출 (sum = 4 - 1 = 3) -> depth == numbers.length, sum == target, answer++
          
      • dfs(numbers, 4, target, 2) 호출 (sum = 3 - 1)
        • ...

---

나의 코드

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){ // 모든 number을 다 사용한 경우
            if(target == sum) answer++; // target 넘버와 같은 경우 경우의수 count
        } else { 
            dfs(numbers, depth + 1, target, sum + numbers[depth]); 
            dfs(numbers, depth + 1, target, sum - numbers[depth]); 
        }
    } 
}