Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8class Solution {
List<String> ans = new ArrayList<>();
public List<String> generateParenthesis(int n) {
solve("", 0, 0, n);
return ans;
}
void solve(String s, int lt, int rt, int n) {
if (s.length() == 2 * n)
ans.add(s);
if (lt < n)
solve(s + "(", lt + 1, rt, n);
if (rt < lt)
solve(s + ")", lt, rt + 1, n);
}
}class Solution {
List<String> ans = new ArrayList<>();
public List<String> generateParenthesis(int n) {
solve(new StringBuilder(), 0, 0, n);
return ans;
}
void solve(StringBuilder sb, int lt, int rt, int n) {
if (sb.length() == 2 * n)
ans.add(sb.toString());
if (lt < n) {
sb.append("(");
solve(sb, lt + 1, rt, n);
sb.setLength(sb.length() - 1);
}
if (rt < lt) {
sb.append(")");
solve(sb, lt, rt + 1, n);
sb.setLength(sb.length() - 1);
}
}
}