#include "molecules.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>
using namespace std;
int l, u;
vector<pair<int, int>> w_sort;
vector<int> out;
unordered_map<string, int> memo;
int dp(int i, int mx, int mn, long long sum) {
string key = to_string(i) + "_" + to_string(mx) + "_" + to_string(mn) + "_" + to_string(sum);
if (memo.count(key))
return memo[key];
if (sum > u || (mx - mn > u - l && mx != 0))
return memo[key] = 0;
if (sum >= l)
return memo[key] = 1;
if (i < 0)
return memo[key] = 0;
if (dp(i - 1, max(mx, w_sort[i].first), min(mn, w_sort[i].first), sum + w_sort[i].first)) {
out.push_back(w_sort[i].second);
return memo[key] = 1;
}
else if (dp(i - 1, mx, mn, sum)) {
return memo[key] = 1;
}
return memo[key] = 0;
}
std::vector<int> find_subset(signed _l, signed _u, std::vector<int> w) {
l = _l;
u = _u;
int n = w.size();
w_sort.resize(n);
vector<int> prefx(n+1);
for (int i = 0; i < n; i++) w_sort[i] = {w[i],i};
sort(w_sort.begin(), w_sort.end());
if (dp(n - 1, 0, 10000000, 0)) {
return out;
}
return std::vector<int>(0);
}
