Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Input
Integer n
Output
all combinations of well-formed parentheses of n pairs of parentheses
Constraints
- 1 <= n ≤ 8
Sample Input
n = 2
Sample Output
["(())","()()"]
Solution
Approach: Recursion
Code Implementation
class Solution {
public:
void solve (int n, int open, int close, int pos,
string str, vector<string>& sol) {
if (pos == 2*n) {
sol.push_back(str);
return;
}
if (open < n) {
str[pos] = '(';
solve(n, open+1, close, pos+1, str, sol);
}
if (open > close) {
str[pos] = ')';
solve(n, open, close+1, pos+1, str, sol);
}
}
vector<string> generateParenthesis(int n) {
string str (2*n, ' ');
vector<string> sol;
solve (n, 0, 0, 0, str, sol);
return sol;
}
};
Time complexity: O(2n)