타겟 넘버

DFS

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

BFS

import java.util.*;
class Solution{
    public int solution(int[] numbers, int target){
    	int answer =0;
        
        Queue<Point> queue = new LinkedList<Point>();
        queue.offer(new Point(numbers[0], 0);
        queue.offer(new Point(-numbers[0], 0);
        
       	while(!queue.isEmpty()){
        	Point p = queue.poll();
            if(p.index == numbers.length-1){
            	if(p.cur == target){
                	answer +=1;
                }
                continue;
       		 }
        	queue.add(new Point(p.cur +numbers[p.index+1], p.index+1));
        	queue.add(new Point(p.cur -numbers[p.index+1], p.index+1));
        }
        
        return answer;
    }
}

class Point{
	int cur;
    int index;
    
    Point(int cur, int index{
    	this.cur = cur;
        this.index = index;
    }
 }