括号。设计一种算法,打印n对括号的所有合法的(例如,开闭一一对应)组合。
说明:解集不能包含重复的子集。
例如,给出 n = 3,生成结果为:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
深度优先搜索 DFS。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def dfs(left, right, t):
if left == n and right == n:
ans.append(t)
return
if left < n:
dfs(left + 1, right, t + '(')
if right < left:
dfs(left, right + 1, t + ')')
dfs(0, 0, '')
return ans
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
dfs(0, 0, n, "", ans);
return ans;
}
private void dfs(int left, int right, int n, String t, List<String> ans) {
if (left == n && right == n) {
ans.add(t);
return;
}
if (left < n) {
dfs(left + 1, right, n, t + "(", ans);
}
if (right < left) {
dfs(left, right + 1, n, t + ")", ans);
}
}
}
function generateParenthesis(n: number): string[] {
let ans = [];
dfs(0, 0, n, '', ans);
return ans;
}
function dfs(left: number, right: number, n: number, t: string, ans: string[]) {
if (left == n && right == n) {
ans.push(t);
return;
}
if (left < n) {
dfs(left + 1, right, n, t + '(', ans);
}
if (right < left) {
dfs(left, right + 1, n, t + ')', ans);
}
}
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
dfs(0, 0, n, "", ans);
return ans;
}
void dfs(int left, int right, int n, string t, vector<string>& ans) {
if (left == n && right == n)
{
ans.push_back(t);
return;
}
if (left < n) dfs(left + 1, right, n, t + "(", ans);
if (right < left) dfs(left, right + 1, n, t + ")", ans);
}
};
func generateParenthesis(n int) []string {
var ans []string
dfs(0, 0, n, "", &ans)
return ans
}
func dfs(left, right, n int, t string, ans *[]string) {
if left == n && right == n {
*ans = append(*ans, t)
return
}
if left < n {
dfs(left+1, right, n, t+"(", ans)
}
if right < left {
dfs(left, right+1, n, t+")", ans)
}
}
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
let res = [];
dfs(n, 0, 0, '', res);
return res;
};
function dfs(n, left, right, prev, res) {
if (left == n && right == n) {
res.push(prev);
return;
}
if (left < n) {
dfs(n, left + 1, right, prev + '(', res);
}
if (right < left) {
dfs(n, left, right + 1, prev + ')', res);
}
}