生成所有有效括号组合的回溯解析（Python，Java，C语言）

题目数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1输出[()]Python解法回溯下同代码示例class Solution: def generateParenthesis(self, n: int) - List[str]: res [] def dfs(path: str,left : int,right : int): if len(path) 2*n: res.append(.join(path)) return if left n: path.append(() dfs(path,left1,right) path.pop() if right left: path.append()) dfs(path,left,right1) path.pop() dfs([],0,0) return res解释1函数结构path当前拼接出来的括号字符串left已经用了几个左括号(right已经用了几个右括号)def dfs(path: str, left: int, right: int):2保存并开始回溯从return后开始回溯总长度必须是2nn 左 n 右if len(path) 2*n: res.append(.join(path)) return3放左括号条件和放右括号的条件二者不能调换注意pop操作只在回溯时使用if left n: path.append(() dfs(path, left 1, right) path.pop() if right left: path.append()) dfs(path, left, right 1) path.pop()图片方便理解Java解法代码示例class Solution { public ListString generateParenthesis(int n) { ListString res new ArrayList(); dfs(res, , n, 0, 0); return res; } private void dfs(ListString res, String s, int n, int left, int right){ if (s.length() 2*n) { res.add(s); return; } if (left n){ dfs(res, s (, n, left 1, right); } if (right left){ dfs(res, s ), n, left, right 1); } } }C语言代码示例char** res; int resSize; void backtrack(char* path, int left, int right, int n) { // 终止条件长度 2n if (strlen(path) 2 * n) { res[resSize] (char*)malloc(2 * n 1); strcpy(res[resSize], path); return; } // 可以加左括号 if (left 0) { // 拼接新字符串传给下一层 char newPath[200]; strcpy(newPath, path); int len strlen(newPath); newPath[len] (; newPath[len 1] \0; backtrack(newPath, left - 1, right, n); // 回溯newPath 是局部变量自动销毁天然回溯 } // 可以加右括号剩余右 剩余左 if (right left) { char newPath[200]; strcpy(newPath, path); int len strlen(newPath); newPath[len] ); newPath[len 1] \0; backtrack(newPath, left, right - 1, n); // 同样天然回溯 } } char** generateParenthesis(int n, int* returnSize) { res (char**)malloc(sizeof(char*) * 10000); resSize 0; // 从空串开始左 n 个右 n 个 backtrack(, n, n, n); *returnSize resSize; return res; }