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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Time Complexity: O(2 ^ n)
*/
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
generate(n, res, 0, 0, "");
return res;
}
void generate(int n, List<String> res, int leftCount, int rightCount, String cur) {
if (cur.length() == n * 2) {
res.add(cur);
return;
}
if (leftCount < n) {
generate(n, res, leftCount + 1, rightCount, cur + "(");
}
if (rightCount < leftCount) {
generate(n, res, leftCount, rightCount + 1, cur + ")");
}
}
}