# 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.

```cpp
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);
}
```