| Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
Description
Given n coins, values of them are A, A ... A respectively, you have to find whether you can pay K using the coins. You can use any coin at most two times.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 18) and K (1 ≤ K ≤ 10). The next line contains n distinct integers denoting the values of the coins. These values will lie in the range [1, 10].
Output
For each case, print the case number and 'Yes' if you can pay K using the coins, or 'No' if it's not possible.
Sample Input
3
2 5
1 2
2 10
1 2
3 10
1 3 5
Sample Output
Case 1: Yes
Case 2: No
Case 3: Yes
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[];
bool dfs(int n,int re,int sh)
{
if(re==||sh==re)return true;
if(n==||re<||re>sh)return false;
if(dfs(n-,re,sh-*a[n]))return true;
if(dfs(n-,re-a[n],sh-*a[n]))return true;
if(dfs(n-,re-*a[n],sh-*a[n]))return true;
return false;
}
int main()
{
int t,n,k,i,j,sum;
scanf("%d",&t);
for(i=; i<=t; i++)
{
sum=;
scanf("%d%d",&n,&k);
for(j=; j<=n; j++)scanf("%d",&a[j]);
sort(a+,a+n+);
for(j=; j<=n; j++)sum+=a[j]<<;
cout<<"Case "<<i<<": ";
if(dfs(n,k,sum))
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}