/* vi:set ts=8 sw=4 sta et:
 *
 * Author: Clark J. Wang <dearvoid at gmail.com>
 *
 * $Date$
 * $HeadURL$
 * $Revision$
 */

#include <iostream>
#include <iomanip>
#include <vector>
#include <sstream>

using namespace std;

typedef vector<unsigned> n_v_t;
typedef vector<n_v_t>    n_vv_t;

n_vv_t *
split_num(unsigned n, unsigned min)
{
    n_vv_t * nvv_1 = new n_vv_t;

    if (n < min) {
        return nvv_1;
    } else if (n < 2 * min) {
        nvv_1->resize(1);
        nvv_1->front().push_back(n);
        return nvv_1;
    }

    for (unsigned i = min; i <= n / 2; ++i) {
        auto_ptr<n_vv_t> nvv_2(split_num(n - i, i));
        for (n_vv_t::iterator it = nvv_2->begin(); it != nvv_2->end(); ++it) {
            it->insert(it->begin(), i);
            nvv_1->push_back(*it);
        }
    }

    nvv_1->resize(nvv_1->size() + 1);
    nvv_1->back().push_back(n);

    return nvv_1;
}

int
main(int argc, char *argv[])
{
    if (argc != 2) {
        cout << "Usage:" << endl;
        cout << "\t" << argv[0] << " <positive integer>" << endl;
        return 1;
    }

    int n = -1;
    istringstream ist(argv[1]);
    ist >> n;
    if (n <= 0) {
        cout << "error: n must be a positive integer" << endl;
        return 1;
    }

    auto_ptr<n_vv_t> nvv(split_num(n, 1));

    ostringstream ost;
    ost << n;
    int nwidth = ost.str().length();

    bool firstline = true;
    for (n_vv_t::iterator vvit = nvv->begin(); vvit != nvv->end(); ++vvit) {
        if (firstline) {
            firstline = false;
            cout << n << " =";
        } else {
            cout << setw(nwidth) << ' ' << " =";
        }
        bool firstnum = true;
        for (n_v_t::iterator vit = vvit->begin(); vit != vvit->end(); ++vit) {
            if (firstnum) {
                firstnum = false;
                cout << " " << *vit;
            } else {
                cout << " + " << *vit;
            }
        }
        cout << endl;
    }
}