22 Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given
n= 3, a solution set is:[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
The Idea: Recursive build from the base case where if n = 0, then sol = { "" }, and if n = 1, then sol = { "()" }. If we continue this pattern, we will notice that every nth case can be built from n-1th case. That is, for every nth case, we insert a parenthesis pair "()" to every left parenthesis. Additionally, we insert a parenthesis pair at the beginning. To take care of duplicates, use an unordered_set. One big problem with this implementation is that we end up calculating a lot of redundent parenthesis sets.
Complexity: 
vector<int> find_left_paren_loc(const string &s) {
vector<int> locs;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(')
locs.push_back(i);
}
return locs;
}
vector<string> _generateParenthesis(int n, vector<string> &prev, unordered_set<string> &unique) {
if (n > 0) {
vector<string> next;
for (string &s : prev) {
vector<string> candidates;
vector<int> left_locs = find_left_paren_loc(s);
for (int i : left_locs) {
string str_cp = s;
candidates.push_back(str_cp.insert(i + 1, "()"));
}
candidates.push_back("()" + s);
for (const string &s1 : candidates) {
if (unique.find(s1) == unique.end()) {
next.push_back(s1);
unique.insert(s1);
}
}
}
return _generateParenthesis(n - 1, next, unique);
}
return prev;
}
vector<string> generateParenthesis(int n) {
unordered_set<string> unique;
vector<string> prev;
prev.push_back("");
return _generateParenthesis(n, prev, unique);
}
int main()
{
for (int i : {0, 1, 2, 3, 4, 5, 6}) {
print(generateParenthesis(i));
cout << endl;
}
}
Solution 2 with optimal time complexity:
Maintain two integers which will denote the number of remaining left and right parenthesis. Initially, we know that we need 
n left parenthesis and as a general rule, we can only have a right parenthesis if the current number of left parenthesis exceeds the number of right parenthesis. For example, if we have 0 left parenthesis, then there is no way we can have a right. However, when we have 2 left parenthesis - we can branch out with a right. So it follows that number of left parenthesis can only decrease, while the number or right parenthesis can only increase only when a left parenthesis is introduced.class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
solutions = []
def __generateParenthesis(cur, left, right):
if left == 0 and right == 0:
solutions.append(cur)
else:
if right:
__generateParenthesis(cur + ')', left, right - 1)
if left:
__generateParenthesis(cur + '(', left - 1, right + 1)
__generateParenthesis('', n, 0)
return solutions
obj = Solution()
print(obj.generateParenthesis(4))
Last modified 3yr ago