더하기
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465
#include <stdio.h>
#define MAXN (20)
int N, K;//자연수 개수, 만들값
int A[MAXN + 10];//자연수 값
int rec[MAXN + 10];//기록(디버깅용)
int presum[MAXN + 10];//prefix sum
int flag;//합계가 K인지 성공여부를 체크
char *msg[] = { "NO", "YES" };
void InputData(void) {
scanf("%d %d", &N, &K);
for (int i = 1; i <= N; i++) {
scanf("%d", &A[i]);
}
}
#if 0
int DFS(int cnt, int start, int sum) {//sum이 k가 되는 모든 경우의 수 시도
if (sum == K) {
//for (int i = 1; i <= N; i++) printf("%d ", rec[i]); printf("\n");
flag = 1;
return;
}
if (sum > K) return;//가지치기
if (cnt > N || start > N) return;
for (int i = start; i <= N; i++) {//A배열의 정수
rec[cnt] = A[i];//기록
DFS(cnt + 1, i + 1, sum + A[i]);
rec[cnt] = 0;
}
}
#else
int DFS(int cnt, int start, int sum) {//sum이 k가 되는 모든 경우의 수 시도
if (K > sum + presum[N] - presum[start - 1]) return 0;//남은 정수를 모두 더해도 K가 될수 없다면 가지치기
if (sum == K) return 1;//성공
if (sum > K) return 0;
if (cnt > N || start > N) return 0;
for (int i = start; i <= N; i++) {//A배열의 정수
if (DFS(cnt + 1, i + 1, sum + A[i]) == 1) return 1;
}
return 0;//실패
}
#endif
int Solve(void) {
int i, ans;
for (i = 1; i <= N; i++) {
presum[i] = presum[i-1] + A[i];
}
//flag = 0;
//DFS(1, 1, 0);//1개부터 시작, A[0]번부터 시작, 합계는 0
ans = DFS(1, 1, 0);
return ans;
}
int main(void) {
int T, t, ans;
scanf("%d", &T);
for (t = 1; t <= T; t++) {
InputData();//입력
ans = Solve();
printf("%s\n", msg[ans]);//출력
}
return 0;
}
C
INFO