一、题目
1、算法题目
“给定一个整数n，生成所有有效的括号组合。”
题目链接：
来源：力扣（LeetCode）
链接：22. 括号生成 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1： 输入： n = 3 输出： ["((()))","(()())","(())()","()(())","()()()"] 复制代码
示例 2： 输入： n = 1 输出： ["()"] 复制代码
二、解题
1、思路分析
这道题可以采用暴力破解法，生成所有字符构成的序列，然后检查有效即可。
2、代码实现
采用递归生成所有序列，然后用左括号数量减去右括号数量，判断序列是否有效，代码参考：
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(22nn)
对于 22nn 个序列中的每一个，我们用于建立和验证该序列的复杂度为 O(n)。
空间复杂度： O(n)
除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。
三、总结
回溯的话，要么设置一个全局的唯一状态，然后去递归。
要么自己管理一个栈或队列，每次储存相应的状态，然后去遍历状态树。
我一般不太喜欢函数递归，因为函数调用稍慢些。
