문제

타겟 넘버

풀이

배열을 준 숫자들을 가지고 목표 값을 만들어내는 것이다. 숫자는 중복이 될 수 있고
연산은 +와 -를 사용할 수 있다. 배열이 상대적으로 작기 때문에 DFS를 사용할 수 있다

static int[] arr;
static int goal;
static int answer;

public static int solution(int[] numbers, int target) {
     arr = numbers;
     goal = target;
     dfs(0, 0);
     return answer;
}

private static void dfs(int depth, int sum) {
	// 종료 조건은 전체 숫자를 가지고 연산하였을때 이다
	if (depth == numbers.length) {
    	// 목표값에 해당하면 만들수 있는 경우의 수를 추가해준다
    	if (sum == goal) {
        	answer++;
        }
        return;
    }
    
    // 배열에 있는 값을 +, -를 둘다 해볼 수 있다
    dfs(depth + 1, sum + arr[depth]);
    dfs(depth + 1, sum - arr[depth]);
}

전체 코드

전체 코드