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);
}
Last modified 3yr ago