题目来源
22. 括号生成 - 力扣（LeetCode）
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示
1 <= n <= 8
题目解析
本题可以通过 “回溯算法” 解题。
回溯算法是基于递归进行的，而递归过程，可以模拟为一颗树的生成过程。
以示例1为例：
树的第一层节点生成
每一层节点都有两种选择：左括号 "(" 或着 右括号 ")"
但是合法的括号组合，不可能以 右括号 开头，因此可以剪去 ‘)’ 分支
树的第二层节点生成
树的第三层节点生成
此时 ()) 分支被剪枝 ，因为其必然不合法。
此时我们可以总结出：如果分支中 左括号 数量 小于 右括号 数量，则生成结果必然不合法。
树的第四层生成
此时需要注意的是，由于 n == 3，因此生成结果中最多只有3个左括号，3个右括号，因此下面绿色框分支中已经用完了左括号，下一层只能选择右括号
树的第五层生成
树的第六层生成，由于合法括号组合必然是以 ) 结尾，因此最后一层必然是右括号
通过上面递归树的过程模拟，我们可以总结出：
递归过程中
- 当前层可选 "左括号" 的条件是：对应分支中，左括号数量未达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[result_size] = (char*)calloc(n * 2 + 1, sizeof(char));strcpy(results[result_size++], path);return;}if (leftCount < n) { // 可选左括号的条件是：当前分支中左括号数量未达n个path[index] = '(';dfs(index + 1, leftCount + 1, rightCount, n);}if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量path[index] = ')';dfs(index + 1, leftCount, rightCount + 1, n);}
}char** generateParenthesis(int n, int* returnSize) {path = (char*)calloc(n * 2 + 1, sizeof(char));path[0] = '('; // 第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] = '('; // 第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[index] = '(';dfs(index + 1, leftCount + 1, rightCount, n);}if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量path[index] = ')';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[n * 2];path[0] = '('; // 第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[index] = '(';dfs(index + 1, leftCount + 1, rightCount, n);}if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量path[index] = ')';dfs(index + 1, leftCount, rightCount + 1, n);}}
}
Python源码实现
class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""path = ['\0'] * n * 2path[0] = '('results = []def dfs(index, leftCount, rightCount):if leftCount == n and rightCount == n:results.append("".join(path))returnif leftCount < n:path[index] = '('dfs(index + 1, leftCount + 1, rightCount)if leftCount > rightCount:path[index] = ')'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] = '('; // 第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[index] = '(';dfs(index + 1, leftCount + 1, rightCount);}if (leftCount > rightCount) { // 可选右括号的条件是：当前分支中左括号数量 > 右括号数量path[index] = ')';dfs(index + 1, leftCount, rightCount + 1);}}dfs(1, 1, 0);return results;
};