[Programmers] 타겟 넘버 - 깊이/너비 우선 탐색(DFS/BFS)

// 타겟 넘버 - 깊이/너비 우선 탐색(DFS/BFS)
public class TargetNum {
	int answer = 0;
	public int solution(int[] numbers, int target) {
		dfs_r(numbers, target, 0); // 0 index에서 시작
		return answer;
	}

	// DFS RECURSIVE 활용
	private void dfs_r(int[] numbers, int target, int index) {

		if (index == numbers.length) { // index가 numbers 배열의 끝에 도달하였을 때 sum을 구하여 target과 같으면 answer를 증가
			int sum = 0;
			for (int ele : numbers) {
				sum += ele;
			}
			if (sum == target) {
				answer++;
			}
		} else { // index가 numbers배열의 끝에 도달하지 못하였다면 +1과 -1을 번갈아 가며 재귀
			numbers[index] *= 1;
			dfs_r(numbers, target, index + 1);

			numbers[index] *= -1;
			dfs_r(numbers, target, index + 1);
		}

	}
}

• DFS RECURSIVE 방식으로 구현