1- A lot of people solved the question using dp but i used bit masing both the logics are same but why bit masking not worked out for me.
LOGIC
creating subsets and findind minimum to the tower of (2*);
DP-CODE
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll int
#define endl ‘\n’
#define vi vector
#define pii pair<ll, ll>
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define fill(a,b) memset(a, b, sizeof(a))
#define setbits(x) __builtin_popcountll(x)
const ll inf=0x3f3f3f3f3f3f3f3f, N = 4e3 + 4;
ll n, k, a[N], pre[N], dp[N][N];
ll call(ll i, ll j) {
if(j >= k) {
ll temp = j + k;
if((pre[i - 1] - j) >= k)return i - 1;
ll p = lower_bound(pre + 1, pre + n + 1, temp) - pre;
return p;
}
if(i == n + 1)return n + 1;
if(dp[i][j] != -1)return dp[i][j];
ll rtn = n + 1;
rtn = min(rtn, call(i + 1, j + a[i]));
rtn = min(rtn, call(i + 1, j));
return dp[i][j] = rtn;
}
int main() {
SPEED;
ll t;
cin>>t;
while(t–) {
cin>>n>>k;
for(ll i = 1; i <= n; i++) {
cin>>a[i];
if(a[i] > k)a[i] = k;
}
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
pre[0] = 0;
for(ll i = 1; i <= n; i++)pre[i] = a[i] + pre[i - 1];
for(ll i = 1; i <= n; i++) {
for(ll j = 0; j <= k; j++) {
dp[i][j] = -1;
}
}
ll ans = call(1, 0);
if(ans == (n + 1)) {
cout<<-1<<endl;
}
else cout<<ans<<endl;
}
return 0;
}
BIT-MASKING CODE
#include
#include
#include
#include
#define ll long long int
#include
#define mod 1000000007
using namespace std;
int main()
{
ll tc;
cin>>tc;
while(tc–)
{
int n=2;
ll size,k,sum=0,chec=0,max=-1,count=0,no=0,res=0;
cin>>size>>k;
k=(2*k);
ll arr[size];
for(ll i=0;i<size;i++)
{
cin>>arr[i];
sum+=arr[i];
}
if(sum==k)
{
cout<<size;
}
else if(sum<k)
{
cout<<"-1";
}
else
{
for(ll i=0;i<(1<<size);i++)
{
count=0;
chec=0;
for(ll j=0;j<size;j++)
{
if(i&(1<<j))
{
chec+=arr[j];
count++;
}
}
if(chec>=k&&count>1&&no==0)
{
max=count;
no=1;
}
if(no==1&&chec>=k&&count<max&&count>1)
{
max=count;
}
}
}
cout<<max<<endl;
}
return 0;
}