#include <bits/stdc++.h>
#include "molecules.h"
#define MAX 500010
using namespace std;
int N, L, U;
int indAnt[MAX];
int valueAnt[MAX];
bool dp[MAX];
vector<int> ans;
void add(int w, int i)
{
for(int g = U ; g >= w ; g--)
{
if(dp[g - w] && !dp[g])
{
dp[g] = true;
indAnt[g] = i;
valueAnt[g] = w;
}
}
}
std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
L = l; U = u;
N = w.size();
//for(int g = 0 ; g < N ; g++)
//printf("%d\n",w[g]);
ans.clear();
memset(dp , false , sizeof(dp));
memset(indAnt , -1 , sizeof(indAnt));
memset(valueAnt , -1 , sizeof(valueAnt));
dp[0] = true;
for(int g = 0 ; g < N ; g++)
add( w[g] , g );
int can = -1;
//for(int g = 1 ; g <= U ; g++)
//printf("-> %d %d\n",g,dp[g]);
for(int g = L ; g <= U ; g++)
{
if(dp[g])
{
can = g;
break;
}
}
//printf("can = %d\n",can);
if(can == -1) return ans;
while( indAnt[can] != -1 )
{
ans.push_back( indAnt[can] );
can -= valueAnt[can];
}
//printf("-> %d\n",ans.size());
return ans;
}
/*int main()
{
scanf("%d %d %d",&N,&L,&U);
vector<int> W(N);
for(int g = 0 ; g < N ; g++)
scanf("%d",&W[g]);
printf("%d\n",find_subset(L , U , W).size());
}*/
