“给定一个整数n,生成所有有效的括号组合。”
题目链接:
来源:力扣(LeetCode)
链接:22. 括号生成 - 力扣(LeetCode) (leetcode-cn.com)
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足:左括号必须以正确的顺序闭合。
示例 1:
输入: n = 3
输出: ["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入: n = 1
输出: ["()"]
这道题可以采用暴力破解法,生成所有字符构成的序列,然后检查有效即可。
采用递归生成所有序列,然后用左括号数量减去右括号数量,判断序列是否有效,代码参考:
public class Solution {
public IList<string> GenerateParenthesis(int n) {
List<string> res = new List<string>();
if (n == 0)
res.Add("");
else
{
for (var i = 0; i < n; i++)
{
foreach (var left in GenerateParenthesis(i))
{
foreach (var right in GenerateParenthesis(n - i - 1))
{
res.Add("(" + left + ")" + right);
}
}
}
}
return res;
}
}
时间复杂度 : O(22nn)
对于 22nn 个序列中的每一个,我们用于建立和验证该序列的复杂度为 O(n)。
空间复杂度: O(n)
除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要 O(1) 的空间,最多递归 2n 层,因此空间复杂度为 O(n)。
回溯的话,要么设置一个全局的唯一状态,然后去递归。
要么自己管理一个栈或队列,每次储存相应的状态,然后去遍历状态树。
我一般不太喜欢函数递归,因为函数调用稍慢些。