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 <= 8
Solution
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtracking("(", 1, 0, n, res);
return res;
}
void backtracking(String s, int open, int closed, int n, List<String> res) {
if (open + closed == 2 * n) {
res.add(s);
return;
}
if (open < n)
backtracking(s + "(", open + 1, closed, n, res);
if (open > closed)
backtracking(s + ")", open, closed + 1, n, res);
}
}