#pragma GCC optimize ("Ofast")
#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back
map<pair<int, int>, int> dp;
vi sb;
int findSubset(int x, int r, vi &w) {
if (r == 0) return 0;
if (x == 0) {
if (w[x] <= r) {
return w[x];
}
return 0;
}
auto it = dp.find(mp(x, r));
if (it != dp.end()) return it->second;
if (w[x] > r) {
return dp[mp(x, r)] = findSubset(x-1, r, w);
}
return dp[mp(x, r)] = max(
findSubset(x-1, r, w),
findSubset(x-1, r-w[x], w) + w[x]
);
}
void constructAns(int x, int r, vi &w) {
if (r == 0) return;
if (x == 0) {
if (w[x] <= r) {
sb.pb(x);
}
return;
}
if (w[x] > r) {
constructAns(x-1, r, w);
return;
}
int c1 = dp[mp(x-1, r)];
int c2 = dp[mp(x-1, r-w[x])] + w[x];
if (c1 > c2) {
constructAns(x-1, r, w);
}
else {
sb.pb(x);
constructAns(x-1, r-w[x], w);
}
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int n = w.size();
findSubset(n-1, u, w);
if (dp[mp(n-1, u)] >= l) {
constructAns(n-1, u, w);
return sb;
}
return vector<int>(0);
}
