Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define INF 0x3F3F3F3F
  4. #define DINF 1e+12
  5. #define rep(i, a, b) for (int i = int(a); i < int(b); i++)
  6. #define pb push_back
  7. #define debug(x) if(1) cout << #x << " = " << x << endl;
  8. #define debug2(x,y) if(1) cout << #x << " = " << x << " --- " << #y << " " << y << "\n";
  9. #define all(S) (S).begin(), (S).end()
  10. #define F first
  11. #define S second
  12. #define EPS 1e-9
  13. #define mp make_pair
  14.  
  15. // freopen("in.txt", "r", stdin);
  16. // freopen("out.txt", "w", stdout);
  17.  
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef pair < int, int >  ii;
  22.  
  23. int K, N;
  24. int v[15];
  25. int cnt;
  26.  
  27. map<vector<int>, bool> m;
  28.  
  29. void printa(int mask){
  30.     bool fi = 1;
  31.     vector<int> vv;
  32.     for(int i=0; i<N; i++) if(mask&(1<<i)){
  33.         vv.pb(v[i]);
  34.     }
  35.     if(!m.count(vv)){
  36.         m[vv] = 1;
  37.         for(int i=0; i<N; i++) if(mask&(1<<i)){
  38.             if(!fi) printf("+");
  39.             fi = 0;
  40.             printf("%d", v[i]);
  41.         }
  42.         printf("\n");
  43.     }
  44. }
  45.  
  46. void solve(int i, int sum, int mask){
  47.     if(sum == K){
  48.         cnt++;
  49.         printa(mask);
  50.         return;
  51.     }
  52.     if(i == N) return;
  53.     if(sum > K) return;
  54.     solve(i+1, sum+v[i], mask|(1<<i));
  55.     solve(i+1, sum, mask);
  56. }
  57.  
  58. int main(){
  59.  
  60.     while(cin >> K >> N && K+N){
  61.         m.clear();
  62.         rep(i, 0, N) cin >> v[i];
  63.         printf("Sums of %d:\n", K);
  64.         cnt = 0;
  65.         solve(0, 0, 0);
  66.         if(!cnt) printf("NONE\n");     
  67.     }
  68.  
  69.     return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement