1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 10, INF = 1e9;
int n, m, w[maxn];
vector<int> ans, temp;
bool cmp(vector<int> a, vector<int> b) {
int al = a.size();
int bl = b.size();
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for (int i = 0; i < al && i < bl; i++) {
if (a[i] != b[i]) return a[i] < b[i];
}
}
void dfs(int id, int sum) {
if(sum>m) return;
if (sum == m) {
if (cmp(temp, ans)) {
ans = temp;
}
return;
}
if (id >= n) return;
temp.push_back(w[id]);
dfs(id + 1, sum + w[id]);
temp.pop_back();
dfs(id + 1, sum);
}
int main() {
scanf("%d%d", &n, &m);
ans.push_back(INF);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
}
dfs(0, 0);
if (ans[0]==INF) printf("No Solution");
else {
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++) {
if (i != 0) printf(" ");
printf("%d", ans[i]);
}
}
return 0;
}
|