I2.cpp

#include<cstdio>
#include<vector>
#include<algorithm>
#define INF 2000000000
#define MAX 36
using namespace std;

int Z, n, S;
vector<int> l;
vector<int> A;
vector<int> B;
bool ok;

void load_data_and_cleaning();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_data_and_cleaning();
    calculate();
    print_data();
  }
  return 0;
}

void load_data_and_cleaning() {
  ok = false; l.clear();
  scanf("%d %d", &n, &S);
  for (int i = 1; i <= n; i++) {
    int tmp;
    scanf("%d", &tmp);
    l.push_back(tmp);
  }
}

vector<int> calculate_sums(int p, int q) {
  vector<int> tmp;
  tmp.push_back(0);
  for (p; p < q; p++) {
     int size = tmp.size() ;
     for (int i = 0; i < size; i++)
       tmp.push_back(l[p] + tmp[i]);
  }
  return tmp;
}

void calculate() {

  if (n == 1 && (l[0] == S || l[0] == 0)) ok = true;

  A = calculate_sums(0, n/2);
  B = calculate_sums(n/2, n);

  //printf("aa: %d %d\n", A.size(), B.size());

  //printf("Sumy: \n");
  //for (int i = 0; i < A.size(); i++) {
    //printf("%d ", A[i]);
  //}
  //printf("\n");

  //printf("Sumy: \n");
  //for (int i = 0; i < B.size(); i++) {
    //printf("%d ", B[i]);
  //}
  //printf("\n");
  
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  int i = 0, j = B.size()-1;

  while (i <= A.size() && j >= 0 && !ok) {
   if (A[i] + B[j] > S) j--;
   else if (A[i] + B[j] < S) i++;
   else ok = true;
  }
}

void print_data() {
  printf(ok ? "TAK\n" : "NIE\n");
}