Shining...

#include<stdio.h>

/*

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 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

출력 예시

YES

*/

#include<stdio.h>

int T;

int N;

int CNT;

int GOAL;

int num[100001];

int dfs(int pos, int cost)

{

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

for (int i = pos; i < N; i++) // 다중트리

{

if (dfs(i + 1, cost + num[i]) == 1) return 1;

}

return 0;

}

int dfs(int pos, int cost)

{

if (pos > cntN)  return 0;

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

if (dfs(pos + 1, cost + arr[pos]) == 1) return 1; // 이진트리

if ( dfs(pos + 1, cost )==1) return 1;

}

void main()

{

scanf("%d", &T);

while (T--)

{

scanf("%d %d", &N, &GOAL);

for (int i = 0; i < N; i++)

{

scanf("%d", &num[i]);

}

printf("%s\n", dfs(0, 0) == 1 ? "YES" : "NO");

}

}