#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;

// Recursively generate all fully parenthesized sums
vector<string> parenthesize(const vector<string> &vars) {
    vector<string> result;

    // Base case: only one variable -> itself
    if (vars.size() == 1) {
        result.push_back(vars[0]);
        return result;
    }

    // Split vars into left and right non-empty parts
    for (size_t split = 1; split < vars.size(); ++split) {
        vector<string> left(vars.begin(), vars.begin() + split);
        vector<string> right(vars.begin() + split, vars.end());

        vector<string> left_parens  = parenthesize(left);
        vector<string> right_parens = parenthesize(right);

        // Combine every left with every right
        for (const string &L : left_parens) {
            for (const string &R : right_parens) {
                result.push_back("(" + L + " + " + R + ")");
            }
        }
    }

    return result;
}

int main() {
    int n;

    cout << "How many numbers do you want to sum? ";
    if (!(cin >> n) || n < 1 || n > 10) {
        cerr << "Please enter a positive integer between 1 and 10.\n";
        return EXIT_FAILURE;
    }

    // Create variable names: a, b, c, d, ...
    vector<string> vars;
    for (int i = 0; i < n; ++i) {
        char name = 'a' + i;  // a, b, c, ...
        string s(1, name);
        vars.push_back(s);
    }

    vector<string> forms = parenthesize(vars);

    cout << "\nThere are " << forms.size()
         << " ways to fully parenthesize the sum of "
         << n << " numbers.\n";

    for (size_t i = 0; i < forms.size(); ++i) {
        cout << i + 1 << ". " << forms[i] << '\n';
    }

    return EXIT_SUCCESS;
}