[Programmers] 타겟 넘버 Java

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java

문제 설명

 

그래프의 모든 정점을 순회하면서 target에 해당하는 계산식을 찾는다.

백트래킹이므로 dfs로 구현한다.

class Solution {
	int count = 0;
	
	public int solution(int[] numbers, int target) {
		int answer = 0;
		
		dfs(numbers, target, 0, 0); // depth, result
		answer = this.count;
		
		return answer;
	}
	
	public void dfs(int[] numbers, int target, int depth, int result) {
		if(depth == numbers.length) {
			if(target == result) this.count++;
			return;
		}
		
		int add = result + numbers[depth];
		int sub = result - numbers[depth];
		
		dfs(numbers, target, depth + 1, add);
		dfs(numbers, target, depth + 1, sub);
	}
	
	
	public static void main(String[] args) {
		Solution solution = new Solution();
		
		int[] numbers = {1, 1, 1, 1, 1};
		int target = 3;
		
		int answer = solution.solution(numbers, target);
		System.out.println("Answer = " + answer);
	}
}