프로그래머스 dfs bfs 타겟넘버 자바

문제 링크

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

풀이

dfs bfs 문제에 속했지만 완전 탐색 방식을 사용했다. 결국 어레이의 모든 노드를 +,-라는 경우의 수를 모두 탐색해야 되서 직감적으로 완전 탐색 방식으로 풀었다. 성능에 큰 차이가 있는지는 공부해 봐야겠다.

코드

import java.util.*;

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