프로그래머스 | 타겟 넘버(DFS)

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

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

 

📖 문제 풀이

 

- DFS에서는 점화식과 종료조건을 찾는 것이 가장 중요하다.

 

 

📖 소스 코드

public class 타겟넘버 {
	public static void main(String[] args) {
		int[] numbers = {1,1,1,1};
		int target =  3;

		System.out.println(solution(numbers, target));
	}

	public int solution(int[] numbers, int target) {
		return DFS(numbers, target, 0, 0);
	}

	public int DFS(int[] numbers, int target, int index, int num) {
		if(index == numbers.length) {
			return num == target ? 1 : 0;
		} else {
			return DFS(numbers, target, index + 1, num + numbers[index])
					+ DFS(numbers, target, index + 1, num - numbers[index]);
		}
	}
	
}

 

참고 :  https://lkhlkh23.tistory.com/74