runtah

Method: Backtracking
Possible optimizations: Used a map to check if a set was generated before, it takes more time than checking if the numbers were used more than they appeared in input

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> nlist;
vector< vector<int> > finlist;
bool used[20];
map< vector<int>, bool > mp;
int btracking(int t, int sum, vector<int> temp, int k) {
 //if (!sum) solve[i].clear();

 if (sum == t) {
 if (!mp[temp]) {
 finlist.push_back(temp);
 mp[temp] = true;
 }
 return 0;
 }

 for (k ; k<nlist.size() ; k++) {
 if (!used[k]) {
 if (nlist[k]<=(t-sum)) {
 sum+=nlist[k];
 temp.push_back(nlist[k]);
 used[k] = true;
 btracking(t, sum, temp, k);
 used[k] = false;
 temp.pop_back();
 sum-=nlist[k];
 }
 }
 }

 return 0;
}

int main( void ) {

 int t, n, i, j, x;

 //freopen("574_in.txt","r+",stdin);

 while ( scanf("%d %d",&t,&n) == 2 ) {
 if (!n) break;

 printf("Sums of %d: ",t);

 nlist.clear();
 for (i=0 ; i<n ; i++) {
 scanf("%d",&x);
 nlist.push_back(x);
 used[i] = false;
 }
 //cout << "-----> " << nlist.size() << endl;

 finlist.clear();
 vector<int> temp;
 temp.clear();
 mp.clear();
 btracking(t, 0, temp, 0);

 if (!finlist.size()) {
 printf("NONE ");
 }

 //printf("--> %d ",finlist.size());
 for (i=0 ; i<finlist.size() ; i++) {
 for (j=0 ; j<finlist[i].size() ; j++) {
 if (!j) printf("%d",finlist[i][j]);
 else printf("+%d",finlist[i][j]);
 }
 printf(" ");
 }

 }

 return 0;
}