代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
括号。设计一种算法,打印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);
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。