//All combinations to get a number.

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

typedef unsigned int uint;

vector<uint> g_summands;

typedef vector<uint> _CombinationContainer;

class Combination
{
    _CombinationContainer _cc;

public:
    Combination(uint capacity = 0)
    {
        _cc.reserve(capacity);
    }
    
public:
    int Add(uint number)
    {
        _cc.push_back(number);
        return _cc.size() - 1;
    }
    void Replace(_CombinationContainer::iterator pos, const Combination &c)
    {
        _cc.erase(pos);
        _cc.insert(_cc.end(), c.begin(), c.end());
        sort(_cc.begin(), _cc.end());
        reverse(_cc.begin(), _cc.end());
    }
    uint Sum() const
    {
        uint r = 0;
        for(_CombinationContainer::const_iterator it = _cc.begin(); it < _cc.end(); it++)
        {
            r += *it;
        }
        return r;
    }
    _CombinationContainer::iterator begin()
    {
        return _cc.begin();
    }
    _CombinationContainer::iterator end()
    {
        return _cc.end();
    }
    _CombinationContainer::const_iterator begin() const
    {
        return _cc.begin();
    }
    _CombinationContainer::const_iterator end() const
    {
        return _cc.end();
    }
    uint operator[](int index)
    {
        return _cc[index];
    }
    const uint operator[](int index) const
    {
        return _cc[index];
    }
};

ostream& operator <<(ostream& op1, const Combination &op2)
{
    bool addPlusSign = false;
    for (_CombinationContainer::const_iterator it = op2.begin(); it < op2.end(); it++)
    {
        op1 << (addPlusSign ? " + " : (addPlusSign = true, "")) << (*it);
    }
    op1 << endl;
    return op1;
}

typedef vector<Combination> CombinationCollection;

CombinationCollection g_combinations;

//Decomposes a number in its minimum number of summands.
bool DecomposeNumber(uint number, Combination &c)
{
    vector<uint>::const_iterator it = g_summands.begin();
    while (it < g_summands.end() && (*it) >= number) it++;
    if (it == g_summands.end()) return false;
    uint n = number;
    do
    {
        //cout << "DecomposeNumber n:  " << n << endl;
        //cout << "DecomposeNumber (*it):  " << *it << endl;
        for (uint i = 0; i < n / (*it); i++) c.Add((*it));
        n -= (n / (*it)) * (*it);
        it++;
    } while (it < g_summands.end() && n);
    /*cout << "DecomposeNumber Sum:  " << c.Sum() << endl;
    if (c.Sum() == number)
    {
        cout << "DecomposeNumber Success:  " << c << endl;
    }
    else if (it >= g_summands.end())
    {
        cout << "DecomposeNumber Failure:  Iterator reached end of summands." << endl;
    }
    else
    {
        cout << "DecomposeNumber Failure:  " << n << endl;
    }*/
    return (c.Sum() == number);
}

void GenerateCombinations(const Combination& c)
{
    uint prevNumber = 0;
    for(_CombinationContainer::const_iterator it = c.begin(); it < c.end(); it++)
    {
        if ((*it) == prevNumber) continue;
        Combination newC = c;
        Combination newSubC;
        if (DecomposeNumber(*it, newSubC))
        {
            newC.Replace(newC.begin() + std::distance(c.begin(), it), newSubC);
            g_combinations.push_back(newC);
            GenerateCombinations(newC);
        }
        prevNumber = *it;
    }
}

void StartGenerateCombinations(uint number)
{
    Combination firstC;
    if (DecomposeNumber(number, firstC))
    {
        g_combinations.push_back(firstC);
        GenerateCombinations(firstC);
    }
}

int main()
{
    cout << "Summands:  ";
    string input;
    getline(cin, input);
    cout << input << endl;
    istringstream in(input);
    while (in.good())
    {
        uint summand;
        in >> summand;
        g_summands.push_back(summand);
    }
    sort(g_summands.begin(), g_summands.end());
    reverse(g_summands.begin(), g_summands.end());
    cout << "Summands input(" << g_summands.size() << "):  ";
    bool addSep = false;
    for (vector<uint>::const_iterator it = g_summands.begin(); it < g_summands.end(); it++)
    {
        cout << (addSep ? ", " : (addSep = true, "")) << (*it);
    }
    cout << endl;
    cout << "Number to decompose:  ";
    uint theNumber;
    input.clear();
    getline(cin, input);
    cout << input << endl;
    in.str(input);
    in.clear();
    in >> theNumber;
    if (!in.fail())
    {
        cout << "Number input to decompose is " << theNumber << "." << endl;
    }
    else
    {
        cout << "Invalid number typed.  Correct input and try again." << endl;
    }
    StartGenerateCombinations(theNumber);
    cout << "Total combinations:  " << g_combinations.size() << endl;
    addSep = false;
    for (CombinationCollection::const_iterator it = g_combinations.begin(); it < g_combinations.end(); it++)
    {
        cout << *it << endl;
    }
    return 0;
}