UVa 574 – Sum It Up


#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int n,t,nums[13];
map <string,char> mymap ;

char* itoa(int val, int base){
    static char buf[32] = {0};
    int i = 30;
    for(; val && i ; --i, val /= base)
        buf[i] = "0123456789abcdef"[val % base];
    return &buf[i+1];
}

void solve(int i, int sum,string collect){
    if (sum == t){
        string T = collect.substr(0,collect.length()-1);
        if (mymap.find(T) == mymap.end()){
            cout<<T<<endl;
            mymap[T]++;
        }
    }else if (sum > t)
        return ;
    else for (int j = i ; j > -1;j--){
        solve(j-1,sum+nums[j],collect+itoa(nums[j],10)+"+");
    }
}

int main()
{
    while (cin>>t>>n &&n&&t){
        for (int i = 0 ; i < n; i++){
            cin>>nums[i];
        }
        cout<<"Sums of "<<t<<":"<<endl;
        sort(nums,nums+n);
        mymap.clear();
        solve(n - 1,0,"");
        if (!mymap.size())
            cout<<"NONE"<<endl;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s