LeetCode - 22 括号生成
标题泉源22. 括号生成 - 力扣（LeetCode）
标题形貌
数字 n 代表生成括号的对数，请你计划一个函数，用于能够生成所有大概的并且 有效的 括号组合。
示例
示例 1：
<strong>输入：</strong>n = 3
<strong>输出：</strong>["((()))","(()())","(())()","()(())","()()()"]
示例 2：
<strong>输入：</strong>n = 1
<strong>输出：</strong>["()"]
提示
[*]1 <= n <= 8
标题剖析
本题可以通过 “回溯算法” 解题。
回溯算法是基于递归进行的，而递归过程，可以模拟为一颗树的生成过程。
以示例1为例：
树的第一层节点生成
每一层节点都有两种选择：左括号 "(" 或着 右括号 ")"
但是正当的括号组合，不大概以 右括号 开头，因此可以剪去 ‘)’ 分支
https://i-blog.csdnimg.cn/direct/aaf4da5521ec4cb8a6ceda6462da823f.png
树的第二层节点生成
https://i-blog.csdnimg.cn/direct/a97797142eb648d997e15572c7ce6d4b.png
树的第三层节点生成
此时 ()) 分支被剪枝 ，由于其必然不正当。
此时我们可以总结出：
如果分支中 左括号 数目 小于 右括号 数目，则生成效果必然不正当。
https://i-blog.csdnimg.cn/direct/2f252bec72f44a079bc230033436176a.png
树的第四层生成
此时需要留意的是，由于 n == 3，因今生成效果中最多只有3个左括号，3个右括号，因此下面绿色框分支中已经用完了左括号，下一层只能选择右括号
https://i-blog.csdnimg.cn/direct/5c6ca12c2f7e4ae1811f8ec41db9d297.png
树的第五层生成
https://i-blog.csdnimg.cn/direct/e7bdcf92f1f549f384827451764a3cd5.png
树的第六层生成，由于正当括号组合必然是以 ) 结尾，因此末了一层必然是右括号
https://i-blog.csdnimg.cn/direct/40b8418c99f84b8b8d6d9a7aa58d5fad.png
通过上面递归树的过程模拟，我们可以总结出：
递归过程中
[*]当前层可选 "左括号" 的条件是：对应分支中，左括号数目未达n个
[*]当前层可选 "右括号" 的条件是：对应分支中，左括号数目 大于 右括号数目
C源码实现
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char* path;
char** results;
int result_size;
void dfs(int index, int leftCount, int rightCount, int n) {
if (leftCount == n && rightCount == n) { // 如果当前分支已经有了n个左括号、n个右括号，则结束递归
results = (char*)calloc(n * 2 + 1, sizeof(char));
strcpy(results, path);
return;
}
if (leftCount < n) { // 可选左括号的条件是：当前分支中左括号数量未达n个
path = '(';
dfs(index + 1, leftCount + 1, rightCount, n);
}
if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量
path = ')';
dfs(index + 1, leftCount, rightCount + 1, n);
}
}
char** generateParenthesis(int n, int* returnSize) {
path = (char*)calloc(n * 2 + 1, sizeof(char));
path = '('; // 第0层肯定选左括号，因为合法的括号组合不可能以右括号开头
results = (char**)malloc(sizeof(char*) * pow(2, 16));
result_size = 0;
dfs(1, 1, 0, n);
*returnSize = result_size;
return results;
}
C++源码实现
class Solution {
public:
vector<char> path;
vector<string> results;
vector<string> generateParenthesis(int n) {
path = vector<char>(n * 2);
path = '('; // 第0层肯定选左括号，因为合法的括号组合不可能以右括号开头
dfs(1, 1, 0, n);
return results;
}
void dfs(int index,int leftCount, int rightCount, int n) {
if (leftCount == n && rightCount == n) { // 如果当前分支已经有了n个左括号、n个右括号，则结束递归
string s(path.begin(), path.end());
results.emplace_back(s);
return;
}
if (leftCount < n) { // 可选左括号的条件是：当前分支中左括号数量未达n个
path = '(';
dfs(index + 1, leftCount + 1, rightCount, n);
}
if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量
path = ')';
dfs(index + 1, leftCount, rightCount + 1, n);
}
}
};
Java源码实现
class Solution {
static char[] path;
static ArrayList<String> results;
public List<String> generateParenthesis(int n) {
path = new char;
path = '('; // 第0层肯定选左括号，因为合法的括号组合不可能以右括号开头
results = new ArrayList<>();
dfs(1, 1, 0, n);
return results;
}
public void dfs(int index, int leftCount, int rightCount, int n) {
if (leftCount == n && rightCount == n) { // 如果当前分支已经有了n个左括号、n个右括号，则结束递归
results.add(new String(path));
return;
}
if (leftCount < n) { // 可选左括号的条件是：当前分支中左括号数量未达n个
path = '(';
dfs(index + 1, leftCount + 1, rightCount, n);
}
if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量
path = ')';
dfs(index + 1, leftCount, rightCount + 1, n);
}
}
}
Python源码实现
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List
"""
path = ['\0'] * n * 2
path = '('
results = []
def dfs(index, leftCount, rightCount):
if leftCount == n and rightCount == n:
results.append("".join(path))
return
if leftCount < n:
path = '('
dfs(index + 1, leftCount + 1, rightCount)
if leftCount > rightCount:
path = ')'
dfs(index + 1, leftCount, rightCount + 1)
dfs(1, 1, 0)
return results
JavaScript源码实现
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
const path = new Array(n * 2);
path = '('; // 第0层肯定选左括号，因为合法的括号组合不可能以右括号开头
const results = [];
function dfs(index, leftCount, rightCount) {
if (leftCount == n && rightCount == n) {// 如果当前分支已经有了n个左括号、n个右括号，则结束递归
results.push(path.join(""));
return;
}
if (leftCount < n) { // 可选左括号的条件是：当前分支中左括号数量未达n个
path = '(';
dfs(index + 1, leftCount + 1, rightCount);
}
if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量
path = ')';
dfs(index + 1, leftCount, rightCount + 1);
}
}
dfs(1, 1, 0);
return results;
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]