1. 더하기 [DFS]

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다.

철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자.

첫 번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다.

두 번째 줄부터 아래 내용이 T개 만큼 주어진다.

첫 줄에 자연수 개수 N(5 <= N <= 20)과 K(1 <= K <= 2,000,000)가 공백으로 구분되어 입력된다.

다음 줄에 N개의 자연수 di(1 <= di <= 100,000)가 공백으로 구분되어 입력된다.

 

T줄에 걸쳐 각 테스트 케이스 별로 주어진 자연수 중 몇 개의 합이 K가 되면 “YES”를 아니면 “NO”를 출력한다.

 

 

입력 예시

2

5 19

1 2 4 7 10

5 25

1 2 4 7 10

출력 예시

문제 풀이 :

 

조건에 맞지 않는 것들은 가지치기를 통해 더이상의 리컬시브가 돌지 않도록 한다.

#include <stdio.h>
int N, K;
int arr[21];
int rec[21];
int flag = 0;
int DFS(int no, int sum) {
	if (sum == K) {
		return 1;
	}
	if (no >= N) {
		//for (int i = 0; i < N; i++)printf("%d ", rec[i]);
		return 0;
	}
	if (sum > K)return 0;    //가지 치기
	rec[no] = arr[no];
	if (DFS(no + 1, sum + arr[no])) return 1;//더하기
	rec[no] = 0;
	if (DFS(no + 1, sum))return 1;//더하지 않기

}
int  main() {
	int ti, T;
	scanf("%d", &T);
	for (ti = 0; ti < T; ti++) {
		int i, ret;
		scanf("%d %d", &N, &K);
		for (i = 0; i < N; i++) scanf("%d", &arr[i]);
		//printf("%d", DFS(0, 0));  //0번 요소부터 시작, 합은 0
		if (DFS(0, 0))printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}