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