Parens

8.9 Parens: Implement an algorithm to print all valid (Le., properly opened and closed) combinations of n pairs of parentheses.

EXAMPLE
Input: 3
Output: ((())), (()()), (())(), ()(()), ()()()

• All valid parenthesis could be built with the base case () or "".

  • For every case forward, we can build every other valid combination by one of two cases: 1) we always insert to the front of the string. 2) for every opening brace ( presents a new opportunity to add and additional (), since we assume that all previous states are valid and therefore so ( guarantees that there will and be ), somewhere later in the string.

  • We perform this procedure for every parenthesis-word, n amount of times that builds off the solutions of the previous.

  • Recursively, I return the next u_set, since I know that every iteration approaches closer solution.

• The bad:

  • A lot of time is wasted checking for duplicates, even though it is O(1) to confirm a duplication.

unordered_set<string> produceParen_rec(unordered_set<string> current, int n, int count) {
    unordered_set<string> new_uset;
    if (count >= n) return current;

    for (string s : current) {
        for (int i = 0; i < s.length(); i++) {
            if (i == 0 || s[i - 1] == '(') {
                string temp = s;
                temp.insert(i, "()");
                new_uset.insert(temp);
            }
        }
    }

    return produceParen_rec(new_uset, n, ++count);
}

unordered_set<string> produceParen(const unsigned n) {
    unordered_set<string> parens = { "" };
    if (n == 0) return parens;

    parens.insert("()");
    return produceParen_rec(parens, n, 1);
}

void print_set(const unordered_set<string> u_set)
{
    int count = 0;
    for (auto i : u_set) 
        cout << count++ << ": " << i << endl;
    pause();
}

int main()
{
    unordered_set<string> parens = produceParen(0);
    print_set(parens);

    parens = produceParen(1);
    print_set(parens);

    parens = produceParen(2);
    print_set(parens);

    parens = produceParen(3);
    print_set(parens);

    parens = produceParen(4);
    print_set(parens);

    parens = produceParen(5);
    print_set(parens);
}