Farjana_akter

Untitled

Aug 8th, 2020
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. vector<ll>v1,v2,coin;
  6.  
  7. void subset(ll i,ll n,ll sum)
  8. {
  9. if(i==n)
  10. {
  11. v1.push_back(sum);
  12. return;
  13. }
  14. subset(i+1,n,sum);
  15. subset(i+1,n,sum+coin[i]);
  16. subset(i+1,n,sum+coin[i]+coin[i]);
  17. }
  18.  
  19. void subset1(ll i,ll n,ll sum)
  20. {
  21. if(i==n)
  22. {
  23. v2.push_back(sum);
  24. return;
  25. }
  26. subset1(i+1,n,sum);
  27. subset1(i+1,n,sum+coin[i]);
  28. subset1(i+1,n,sum+coin[i]+coin[i]);
  29. }
  30.  
  31.  
  32.  
  33. int main()
  34. {
  35. ll t,i,j,k,n,m,a,b,c,d,e;
  36. scanf("%lld",&t);
  37. for(ll cas=1; cas<=t; cas++)
  38. {
  39. coin.clear();
  40. v1.clear();
  41. v2.clear();
  42. scanf("%lld %lld",&n,&k);
  43. for(i=0; i<n; i++)
  44. {
  45. cin>>e;
  46. coin.push_back(e);
  47. }
  48. a=n/2;
  49. subset(0,a,0);
  50. subset1(a,n,0);
  51.  
  52.  
  53. sort(v1.begin(),v1.end());
  54. sort(v2.begin(),v2.end());
  55.  
  56.  
  57. bool flag=false;
  58. cout<<"Case "<<cas<<": ";
  59. for(i=0; i<v2.size(); i++)
  60. {
  61. if(binary_search(v2.begin(),v2.end(),k-v1[i]))
  62. {
  63. flag=true;
  64. break;
  65. }
  66. }
  67. if(flag)
  68. cout<<"Yes"<<endl;
  69. else
  70. cout<<"No"<<endl;
  71. }
  72. }
Advertisement
Add Comment
Please, Sign In to add comment