[프로그래머스] 타켓 넘버 - 자바

https://programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

1. 풀이

---

DFS를 사용하는 문제인데요, 재귀를 사용하여 부분 집합의 알고리즘을 이용하면 쉽게 풀이가 됩니다.

 

배열(numbers)의 요소들을 하나의 노드라고 보고, 문제에서 +, -만을 사용할 수 있다고 하였기 때문에 

 

트리 형태처럼 +와 -를 번갈아주면서 부분집합을 구한 후 합을 구하여 타켓과 같으면 카운트를 해주면 됩니다.

 

저도 처음엔 이해가 잘 안되서, 구글링을 통해서 해당 방법을 알게되었습니다. DFS에 대한 좋은 공부였습니다.

 

2. 코드

---

class Solution {
    static int result = 0;
	
	public static int solution(int[] numbers, int target) {
        dfs(0, numbers, target);
        return result;
    }
	
	public static void dfs(int n, int[] numbers, int target) {
		// 기저 사례 (탈출 조건)
		if(n == numbers.length) {
			int sum = 0;
			for(int i = 0; i < numbers.length; i++)
				sum+=numbers[i];
			if(sum == target)
				result++;
			return;
		} else {
			// +
			numbers[n]*=1;
			dfs(n+1, numbers, target);
			
			// -
			numbers[n]*=-1;
			dfs(n+1, numbers, target);
		}
    }
}