[UVa] 574 - Sum It Up

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 574 - Sum It Up
Source            : UVa Online Judge
Category          : Backtrack
Algorithm         : Backtrack
Verdict           : Accepted 

#include <bits/stdc++.h>
 
using namespace std;
 
#define VI        vector<int>
#define pb        push_back
 
VI ans;
int sum, arr[15];
int amount, n;
string str;
 
bool isSol;
 
map <VI, bool> m;
map <int, int> vis;
 
void combination(int pos, int n)
{
    if (sum == amount)
    {
        if (!m[ans])
        {
            int len = ans.size();
            for (int i=0; i<len; i++)
            {
                cout << ans[i];
                if (i == len-1) cout << endl;
                else cout << "+";
            }
        }
        m[ans] = true;
        isSol = true;
        return;
    }
    for (int i=pos; i<n; i++)
    {
        if (vis[i]) continue;
        vis[i] = 1;
        sum += arr[i];
        ans.push_back(arr[i]);
 
        combination(i+1, n);
 
        vis[i] = 0;
        sum -= arr[i];
        ans.pop_back();
    }
}
 
int main()
{
//   freopen("in.txt", "r", stdin);
//   freopen("out.txt", "w", stdout);
 
   ios::sync_with_stdio(0);
   cin.tie(0);
   while (cin >> amount >> n)
   {
        if (amount+n == 0) return 0;
        for (int i = 0; i < n; i++) cin >> arr[i];
        isSol = false;
        cout << "Sums of " << amount << ":\n";
        combination(0, n);
        if (!isSol) cout << "NONE" << endl;
        m.clear();
   }
   return 0;
}