22. 括号生成
22. 括号生成
题目
Given n
pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8
题目大意
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
解题思路
- 定义一个空数组
res
用于存储最终结果,以及一个空数组track
用于存储当前生成的括号组合。 - 编写回溯函数
backtrack
,该函数接收两个参数left
和right
,分别表示当前已使用的左括号和右括号的数量。 - 在回溯函数中,通过判断条件进行剪枝:
- 如果
left
小于right
,说明生成的括号组合是无效的,直接返回。 - 如果
left
或right
的数量超过n
,说明已经超出有效范围,直接返回。
- 如果
- 如果
left
和right
都等于n
,则说明已经生成了有效的括号组合,将当前track
中的括号组合转为字符串并加入res
数组。 - 在回溯函数中,分别尝试添加左括号和右括号,并递归调用下一层。之后需要撤销当前的选择,继续尝试下一个选择。
- 调用回溯函数
backtrack
的初始状态是(0, 0)
,表示左右括号的数量都为 0。 - 最终返回结果数组
res
。
空间复杂度
- 时间复杂度:
O(4^n / √n)
,生成合法括号组合的时间复杂度由卡特兰数决定,对于n
对括号,其数量为C(2n, n)/(n + 1)
,即O(4^n / √n)
。 - 空间复杂度:
O(n)
(不包括结果数组的存储空间)。- 递归栈的空间复杂度
O(n)
,回溯的最大递归深度为2n
,因为每次递归都会处理一个括号,直到所有2n
个括号被处理完; - 使用了一个
track
数组来存储当前路径,它的空间复杂度是O(n)
。
- 递归栈的空间复杂度
代码
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
let res = [];
let track = [];
const backtrack = (left, right) => {
if (left < right || left > n || right > n) return;
if (left == n && right == n) {
res.push(track.join(''));
return;
}
track.push('(');
backtrack(left + 1, right);
track.pop();
track.push(')');
backtrack(left, right + 1);
track.pop();
};
backtrack(0, 0);
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
17 | 电话号码的字母组合 | [✓] | 哈希表 字符串 回溯 | |
20 | 有效的括号 | [✓] | 栈 字符串 | |
2116 | 判断一个括号字符串是否有效 | 栈 贪心 字符串 |