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

코딩테스트연습(DFS,BFS) - 타겟 넘버

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

프로그래머스

문제 설명

[1,1,1,1,1]로 3을 만드는 경우

양의 정수가 담겨있는 배열 numbers와 만들어야하는 수 target이 주어진다. 

이 숫자들 사이에 +와 -를 적절히 사용하여 target을 만들 수 있는 경우의 수를 구하는 문제이다.

---

문제 풀이

생각 과정

모든 경우의 수를 구해야하므로 dfs를 사용하여 풀기로 하였다. 각 숫자들마다 +와 -를 대입하여 계산하고
모든 숫자를 계산하였을 때 결과가 target과 같으면 count를 늘려주는 방식으로 생각했다.

구현

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