UVa - 624 - CD

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. vector <int> length, ans, anss;
5. int n, track, visit[25], sum, f, minn, sum2;
6.  
7. void start(int index){
8.     if(sum == n){
9.         f = 1;
10.         int sz2 = ans.size();
11.         for(int i = 0; i < sz2; i++)cout << ans[i] << " ";
12.         cout << "sum:" << n << endl;
13.         return;
14.     }
15.     if(sum > n)return;
16.     for(index; index < track; index++){
17.         if(!visit[index]){
18.             visit[index] = 1;
19.             ans.push_back(length[index]);
20.             sum += length[index];
21.             if(sum < n){
22.                 if(minn > (n-sum)){
23.                     minn = n-sum;
24.                     anss.clear();
25.                     int sz = ans.size();
26.                     for(int i = 0; i < sz; i++)anss.push_back(ans[i]);
27.                 }
28.             }
29.             start(index+1);
30.             if(f)break;
31.             visit[index] = 0, ans.pop_back();
32.             sum -= length[index];
33.         }
34.     }
35. }
36.  
37. int main(){
38.     int mn;
39.     while(cin >> n >> track){
40.         sum = 0, f = 0, minn = 123456789, sum2 = 0;
41.         memset(visit, 0, sizeof(visit));
42.         for(int i = 1; i <= track; i++)cin >> mn, length.push_back(mn);
43.         start(0);
44.         if(!f){
45.             for(int i = 0; i < anss.size(); i++)cout << anss[i] << " ", sum2 += anss[i];
46.             cout << "sum:" << sum2 << endl;
47.         }
48.         length.clear(), ans.clear(), anss.clear();
49.     }
50.     return 0;
51. }