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

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

Last updated