Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
题意: 给定一个长度，生成所有此长度的合法括号序列。
Solution1：Backtracking.
We can observe that two constraints:
(1) left Parentheses should come faster ahead to reach given n.
(2) in each level, we increment left Parentheses count (or right Parentheses count) from given n, and add '(' (or ')') into path
At last, left and right Parentheses count become 0, we can gerenate a result path.
code:
/*
Time: O(2^n).
Space: O(n). use O(n) space to store the sequence(path)
*/
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n == 0) return result;
helper("", n, n, result);
return result; } private void helper(String path, int left, int right, List<String> result) {
// corner
if (left > right) return;
// base
if (left == 0 && right == 0) {
result.add(path);
return;
}
if (left > 0) {
helper(path + "(", left - 1, right, result);
}
if (right > 0) {
helper(path + ")", left, right - 1, result);
}
}
}