[Algorithm] 프로그래머스_타겟넘버(JAVA)

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

프로그래머스

 

---

이 문제는 모든 경우의 수를 생각해야 하므로 dfs 알고리즘을 사용한다.

 

이런 그림을 그려가며 접근을 했고

 

sum = 0 + numbers[0] + numbers[1] ...numbers[idx]

sum = 0 - numbers[0] + numbers[1] ...numbers[idx]

...

idx값이 주어지는 배열 길이가 되었을때 재귀문을 빠져나온다.

 

이때 sum이 target값과 같다면 answer 값을 +1 해준다.

 

위 내용을 토대로 구현한 코드는 아래와 같다.

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