타겟 넘버 (DFS/BFS)

INPUT

n개의 음이 아닌 정수, 타겟 넘버

조건

n개의 정수 사이에 적절히 덧셈/뺄셈을 추가하여 타겟 넘버를 만든다.

OUTPUT

n 개의 정수로 타겟 넘버를 만들 수 있는 방법의 수

LOGIC

재귀를 이용하여 탐색하면 된다. 총 2가지 방법이 있으므로 (더하기, 빼기), 재귀를 이용해 완전탐색을 실시한다.

1. 두가지 방법으로 (더하기/빼기) numbers에서 등장하는 숫자를 이용해 계산해 나간다.
2. 만들어진 숫자가 모든 숫자를 사용한 상태이고, 타겟 넘버와 같다면 횟수를 증가시켜준다.

class Solution {
    static int[] mult = new int[]{-1,1};
    static int count=0;
    public int solution(int[] numbers, int target) {
        calc(0,0,numbers,target);
        return count;
    }
    
    public void calc(int index, int sum, int[] numbers, int target){
        //System.out.println("인덱스: "+index+" 합: "+ sum+" 타겟넘버: "+ target);
        if(index==numbers.length){
            if(sum!=target){
                return;
            }else{
                count++;
            }
        }else{
            for(int i=0;i<2;i++){
                calc(index+1,sum+mult[i]*numbers[index],numbers,target);
            }
        }
        
    }
}