더하기

#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;
}