Paying Up

Problem Statement

In the mysterious country of Byteland, everything is quite different from what you'd normally expect. In most places, if you were approached by two mobsters in a dark alley, they would probably tell you to give them all the money that you have. If you refused, or didn't have any - they might even beat you up.
In Byteland the government decided that even the slightest chance of someone getting injured has to be ruled out. So, they introduced a strict policy. When a mobster approaches you in a dark alley, he asks you for a specific amount of money. You are obliged to show him all the money that you have, but you only need to pay up if he can find a subset of your banknotes whose total value matches his demand. Since banknotes in Byteland can have any positive integer value smaller than one thousand you are quite likely to get off without paying.
Both the citizens and the gangsters of Byteland have very positive feelings about the system. No one ever gets hurt, the gangsters don't lose their jobs, and there are quite a few rules that minimize that probability of getting mugged (the first one is: don't go into dark alleys - and this one is said to work in other places also).

Input

The first line contains integer t, the number of test cases (about 100). Then t test cases follow. Each test case starts with n, the number of banknotes in your wallet, and m, the amount of money the muggers asked of you. Then n numbers follow, representing values of your banknotes. Your wallet does not hold more than 20 banknotes, and the value of a single banknote is never more than 1000.

Output

For each test case output a single line with the word 'Yes' if there is a subset of your banknotes that sums to m, and 'No' otherwise.

Example

Input:
5
3 3
1
1
1
5 11
1
2
4
8
16
5 23
1
2
4
8
16
5 13
1
5
5
10
10
20 132
17
6
4
998
254
137
259
153
154
3
28
19
123
542
857
23
687
35
99
999

Output:
Yes
Yes
Yes
No
Yes

Explanation: For example, in the last case you have to pay up, since: 6+3+123=132.

Problem Link : MARCHA1

The idea : 

The idea  is to find  whether there exists a valid subset whose sum is equal to a given number. Now there is a dynamic programming approach to this . However what I used is  the bitwise approach.

The bitwise approach : 

We all know the concept of a boolean hash . Here a 0 or false means that a number is not included and 1 means that a number is included.

Now instead of using an array for hashing purpose we may use a number.  An array of size 'n' may be easily replaced by a number with 'n' no of bits. So a number  2 or '10' would mean that the element corresponding to 1 is present and element corresponding to 0 is not taken.

So now all we need to do is generate all possible combination of  'n' bits . Now this can be done easily by iterating from  0 to 2^n-1. And we would add each element if it is present i.e it's corresponding digit is 1. Else we would simply not add it. Now we just have to compare with the given sum.

Now, the limit on the number of banknotes is 'n'. Let us see how many subsets exist for these banknotes. For finding the number of subsets, we see that for every banknote, we have two choices, either to choose it in our calculation for the sum of notes or to ignore it in calculating the sum. Thus, we have 2 options per banknote and 'n' banknotes. So, the total number of subsets thus becomes 2^n where ^ represents the power operation. The number of subsets are small enough for us to bruteforce through them and the program to run in time.

An interesting way to generate all subsets of 'n' objects when 'n' is considerably small (n <= 20) is to use the properties of how unsigned integers are stored. Consider the number 2^n. This number is represented in binary form as '10000...0', that is, 1 followed by n 0s. Also, any number containing a 1 at the some position will surely be greater than 2^n. Thus, all numbers below 2^n do not have a 1 in a position greater than or equal to 'n' starting from the LSB. By induction, we can do the same for values of n = n-1 and n-2 and so on. Thus, we can see that any number between 2^(n-1) and 2^n will have a 1 in the position n-1. Extending this logic, we can say that if we consider the numbers from 1 to 2^n, we would be considering all possible ways in which we can choose some objects from 'n' objects.

For example, consider n = 3, so 2^n = 8. Let us list 'i' and its binary representation
i    Binary representation using 'n' bits
0    000
1    001
2    010
3    011
4    100
5    101
6    110
7    111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of 'n' objects by looping over numbers from 1 to 2^n.

For calculating the sum of the subset represented by 'i', we loop from 0 to 'n' and we check whether the corresponding bit is set in the value for 'i' or not. If it is, we include that object in calculating our sum else we don't. In this way, we can get the sum for all possible subsets of the 'n' objects.

This is exactly what we need for this problem. After taking in the number of objects, we loop 'i' from 1 to 2^n incrementing the value of 'i' by 1 at every stage to give us a new subset. Then for a particular value of 'i', we loop 'j' from 0 to n and check if the bit at that particular value is set or not. Languages like C / C++ provide bit-wise operators for leftshift and rightshift. For checking if the bit is set at position 'j'(starting from 0) we can just check if the value of (i & (1<<j)) is 0. If it is 0, then the bit is not set, while if it is greater than 0, then the bit is set. Alternatively, we can also loop from 0 to n and at each stage check whether 'i' modulo 2 is equal to 1 or not. If it is 1, then the bit at that position is set, else it's not. Then we divide 'i' by 2 and proceed. At the end of the 'n' iterations, 'i' will equal 0. The problem with this appraoch is that the modulo operations take much more time compared to the bitwise operations. Thus, now that we know how to check if the bit is set, we initialize a value 'sum' equal to 0 at the start of the 'n' iterations for a value of 'i' and if the bit at position 'j' is set, we add the corresponding banknote value to 'sum' else we don't. At the end of these iterations, we check if the value of 'sum' equals the required value. If it does, then we have found a subset with the required sum and so we print a "Yes" and exit. Else, if at the end of 2^n iterations of 'i' we don't have a subset with the required sum, then we print a "No" and exit.

The program should look something like this :

[code]

Start

Take in the value of 'n' and the required value of sum 'm'

Take in all the values for the banknotes in array 'd[]'

For i = 1 and i < (2^n)

sum = 0

For j = 0 and j < n

if jth bit of i is set

sum = sum + d[j]

if sum equals m

print Yes and return

Print No and return

[/code]

 Problem Code: 

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
       long long int n,m;
        scanf("%lld %lld",&n,&m);
        vector<int> v;
        for(int i=0;i<n;i++)
        {
           int k;
           cin>>k;
           v.push_back(k);
        }
        bool check=false;
        for(long long int i=1;i<pow(2,n);i++)
        {
            long long int sum=0;
            for(long long int j=0;j<n;j++)
            {
               if((1<<j) & i)
               sum+=v[j];
              
            }
            if(sum==m)
            check=true;
        }
        if(check)
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
       
    }
    return 0;
}