[Programmers] 타겟넘버 - Java

Level 2

코딩테스트 연습 - 타겟 넘버

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

문제 풀이

DFS 문제

값을 빼고 재귀함수에 넣고, 값을 더해서 재귀함수에 넣어준다.

n이 주어진 숫자의 개수와 같아지면 target과 같은지 확인하고 맞으면 개수+1을 해준다.

 

코드

class Solution {
	public int count = 0;
	
	public void dfs(int res, int n, int[] numbers, int target) {
		if (n == numbers.length) {
			if (res == target) {
				count += 1;
			}
			return;
		}
		
		dfs(res-numbers[n], n+1, numbers, target);
		dfs(res+numbers[n], n+1, numbers, target);
	}
	
	public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        
        return count;
    }
	
}