[programmers] 타겟 넘버

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

프로그래머스

 

---

< 타겟 넘버 >

 

문제 풀이 (Java)

class Solution {
	static int answer;

	public int solution(int[] numbers, int target) {
		answer = 0;

		dfs(numbers, 0, target, 0);

		return answer;
	}

	private void dfs(int[] numbers, int sum, int target, int idx) {
		if (idx == numbers.length) {
			if (target == sum) {
				answer += 1;
			}
			return;
		}

		dfs(numbers, sum + numbers[idx], target, idx + 1);
		dfs(numbers, sum - numbers[idx], target, idx + 1);

	}
}

 

dfs를 호출한 뒤 answer을 반환한다. 

 

dfs 함수에서는 idx가 numbers 끝까지 탐색했다면 return 한다. 이때, target 값과 sum 값이 같다면 answer에 1을 더해준다. 아직 탐색 중이라면 다음 값을 위해 idx+1로 dfs를 호출하며 각 +일 때와 -일 때를 구한다. 

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges