拓冰网站定制 
题目描述数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1输出[()]解题思路方法一回溯 剪枝有效括号的条件左括号数量 ≤ n右括号数量 ≤ 左括号数量否则会出现)(这种无效组合左括号数量 右括号数量 n时得到一个有效组合回溯三步选择放左括号或右括号递归继续生成下一个括号撤销删除当前括号具体过程示例n 2 / \ ( (不合法右括号多于左括号) / \ (( () / \ \ (() ()( ()) ← ()) 不合法右括号多于左括号 / \ (()) ()()有效组合(())、()()代码实现class Solution { public: vectorstring generateParenthesis(int n) { vectorstring result; string path; backtrack(n, 0, 0, path, result); return result; } private: void backtrack(int n, int left, int right, string path, vectorstring result) { // 终止条件左右括号都用完了 if (left n right n) { result.push_back(path); return; } // 选择左括号只要左括号没用完 if (left n) { path.push_back((); backtrack(n, left 1, right, path, result); path.pop_back(); // 撤销 } // 选择右括号只要右括号数量 左括号数量 if (right left) { path.push_back()); backtrack(n, left, right 1, path, result); path.pop_back(); // 撤销 } } };复杂度分析维度复杂度说明时间复杂度O(4^n / √n)第 n 个卡特兰数约等于 4^n / (n√n)空间复杂度O(n)递归栈深度 path 长度卡特兰数C(2n, n) / (n 1)是有效括号组合的数量。关键细节1. 为什么right left才能放右括号因为有效括号要求任意前缀中左括号数量 ≥ 右括号数量。如果right left放右括号会导致)多于(形成无效组合。2. 为什么left n才能放左括号因为总共只有n对括号左括号最多放n个。3. 为什么不用判断right n因为right left已经隐含了right n因为left ≤ n。4. 终止条件为什么是left n right n当左右括号都用完时path就是一个完整的有效组合。方法二暴力枚举生成所有2^(2n)个括号组合然后验证每个是否有效。代码实现class Solution { public: vectorstring generateParenthesis(int n) { vectorstring result; generateAll(n, 0, , result); return result; } private: void generateAll(int n, int pos, string current, vectorstring result) { if (pos 2 * n) { if (isValid(current)) result.push_back(current); return; } generateAll(n, pos 1, current (, result); generateAll(n, pos 1, current ), result); } bool isValid(string s) { int balance 0; for (char c : s) { if (c () balance; else balance--; if (balance 0) return false; } return balance 0; } };复杂度时间 O(2^(2n) × n)空间 O(n)缺点枚举了大量无效组合效率低。方法三动态规划思路n对括号的组合 (i对括号 )n-1-i对括号代码实现class Solution { public: vectorstring generateParenthesis(int n) { vectorvectorstring dp(n 1); dp[0] {}; for (int i 1; i n; i) { for (int j 0; j i; j) { for (string left : dp[j]) { for (string right : dp[i - 1 - j]) { dp[i].push_back(( left ) right); } } } } return dp[n]; } };复杂度时间 O(4^n / √n)空间 O(4^n / √n)三种方法对比方法时间复杂度空间复杂度推荐度回溯 剪枝O(4^n / √n)O(n)⭐⭐⭐⭐⭐暴力枚举O(2^(2n) × n)O(n)⭐⭐动态规划O(4^n / √n)O(4^n / √n)⭐⭐⭐总结要点说明核心思想回溯放左括号或右括号剪枝保证有效关键条件left n放左括号right left放右括号时间复杂度O(4^n / √n)空间复杂度O(n) 【回溯-2】22.括号生成
题目描述数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1输出[()]解题思路方法一回溯 剪枝有效括号的条件左括号数量 ≤ n右括号数量 ≤ 左括号数量否则会出现)(这种无效组合左括号数量 右括号数量 n时得到一个有效组合回溯三步选择放左括号或右括号递归继续生成下一个括号撤销删除当前括号具体过程示例n 2 / \ ( (不合法右括号多于左括号) / \ (( () / \ \ (() ()( ()) ← ()) 不合法右括号多于左括号 / \ (()) ()()有效组合(())、()()代码实现class Solution { public: vectorstring generateParenthesis(int n) { vectorstring result; string path; backtrack(n, 0, 0, path, result); return result; } private: void backtrack(int n, int left, int right, string path, vectorstring result) { // 终止条件左右括号都用完了 if (left n right n) { result.push_back(path); return; } // 选择左括号只要左括号没用完 if (left n) { path.push_back((); backtrack(n, left 1, right, path, result); path.pop_back(); // 撤销 } // 选择右括号只要右括号数量 左括号数量 if (right left) { path.push_back()); backtrack(n, left, right 1, path, result); path.pop_back(); // 撤销 } } };复杂度分析维度复杂度说明时间复杂度O(4^n / √n)第 n 个卡特兰数约等于 4^n / (n√n)空间复杂度O(n)递归栈深度 path 长度卡特兰数C(2n, n) / (n 1)是有效括号组合的数量。关键细节1. 为什么right left才能放右括号因为有效括号要求任意前缀中左括号数量 ≥ 右括号数量。如果right left放右括号会导致)多于(形成无效组合。2. 为什么left n才能放左括号因为总共只有n对括号左括号最多放n个。3. 为什么不用判断right n因为right left已经隐含了right n因为left ≤ n。4. 终止条件为什么是left n right n当左右括号都用完时path就是一个完整的有效组合。方法二暴力枚举生成所有2^(2n)个括号组合然后验证每个是否有效。代码实现class Solution { public: vectorstring generateParenthesis(int n) { vectorstring result; generateAll(n, 0, , result); return result; } private: void generateAll(int n, int pos, string current, vectorstring result) { if (pos 2 * n) { if (isValid(current)) result.push_back(current); return; } generateAll(n, pos 1, current (, result); generateAll(n, pos 1, current ), result); } bool isValid(string s) { int balance 0; for (char c : s) { if (c () balance; else balance--; if (balance 0) return false; } return balance 0; } };复杂度时间 O(2^(2n) × n)空间 O(n)缺点枚举了大量无效组合效率低。方法三动态规划思路n对括号的组合 (i对括号 )n-1-i对括号代码实现class Solution { public: vectorstring generateParenthesis(int n) { vectorvectorstring dp(n 1); dp[0] {}; for (int i 1; i n; i) { for (int j 0; j i; j) { for (string left : dp[j]) { for (string right : dp[i - 1 - j]) { dp[i].push_back(( left ) right); } } } } return dp[n]; } };复杂度时间 O(4^n / √n)空间 O(4^n / √n)三种方法对比方法时间复杂度空间复杂度推荐度回溯 剪枝O(4^n / √n)O(n)⭐⭐⭐⭐⭐暴力枚举O(2^(2n) × n)O(n)⭐⭐动态规划O(4^n / √n)O(4^n / √n)⭐⭐⭐总结要点说明核心思想回溯放左括号或右括号剪枝保证有效关键条件left n放左括号right left放右括号时间复杂度O(4^n / √n)空间复杂度O(n)