[프로그래머스] 타켓 넘버 Java 풀이

프로그래머스

 

접근

DFS를 활용하여 모든 경우의 수를 탐색합니다. 주어진 숫자 배열에서 각 숫자를 더하거나 빼는 모든 경우의 수를 재귀적으로 탐색하여 타겟 넘버를 만들 수 있는 방법의 수를 계산합니다.

 

코드

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