Generate Parentheses
LeetCode #22 · Medium · Backtracking · C++ solution with worked-out approach and complexity analysis.
Approach
Backtracking
Use recursion to build the string. Keep track of the number of open and close parentheses used. We can add an open parenthesis if open < n. We can add a close parenthesis if close < open. When the string length reaches 2*n, we have a valid combination.
Time
O(4^n / sqrt(n))
Catalan number
Space
O(n)
recursion stack and string storage
Problem description(from LeetCode)
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Examples
Example 1
- Input:
- n = 3
- Output:
- ["((()))","(()())","(())()","()(())","()()()"]
Constraints
- •1 <= n <= 8
C++ Solution
solution.cpp
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> v;
helper("", v, 0, 0, n);
return v;
}
void helper(string s, vector<string> &v, int open, int close, int max) {
if (s.size() == 2 * max) {
v.push_back(s);
return;
}
if (open < max) helper(s + "(", v, open + 1, close, max);
if (close < open) helper(s + ")", v, open, close + 1, max);
}
};