#include #include #include #include #include #include #include #include #define setBit(x,b) ((x)|(1<<(b))) #define getBit(x,b) ((x)&(1<<(b))) #define N_MAX 31 #define S_MAX 310000000 #define P_MAX 10000000 using namespace std; typedef struct { int no; int P; }Goods; int N, S; Goods G[N_MAX]; vector ans; int max_p[N_MAX]; bool compG(const Goods& x, const Goods& y) { return x.P > y.P; } void DP(int t, int n, int op) { if (t == 0 && n >= N) { bool first = true; stringstream str; for (int i = 1; i <= N; ++i) { if (getBit(op, i)) { if (!first) str << " "; str << i; first = false; } } ans.push_back(str.str()); return; } if (t < 0 || n >= N || max_p[n] < t) return; DP(t - G[n].P, n + 1, setBit(op, G[n].no)); DP(t, n + 1, op); } void calc() { sort(G, G + N, compG); max_p[N - 1] = G[N - 1].P; for (int i = N - 2; i >= 0; --i) { max_p[i] = max_p[i + 1] + G[i].P; } DP(S, 0, 0); sort(ans.begin(), ans.end()); } int main() { cin >> N >> S; for (int i = 0; i < N; ++i) { G[i].no = i + 1; cin >> G[i].P; } calc(); for (vector::iterator it = ans.begin(); it != ans.end(); ++it) cout << *it << endl; return 0; }