[leetcode]22. Generate Parentheses生成括号

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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);
}
}
}