《程序员面试金典（第6版）》面试题 08.09. 括号（回溯算法，特殊的排列问题，C++）

题目描述

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

["((()))","(()())","(())()","()(())","()()()"
]

解题思路与代码

这道题抽象总结出来，就只有两条规则，分别是：

• 左括号的数量不能多于n
• 右括号的数量不能多于左括号

方法一 ： 回溯法

这道题我看了一下，比较适合用回溯法去解决。

• 我们需要一个辅助函数backtracking，它一共需要设置这么几个参数，分别是左括号的数量left，右括号的时候，right，n的大小n，存储结果集的向量result，一个string用来放括号字符str，共5个参数。

• 写一道回溯算法的题的时候，一般是先去想，这算法该如何返回。那么当str的长度等于2倍的n时，就该返回了，把str存入result后返回

• 之后我们就要去做判断了。这道题和一般的回溯算法不一样，我们这里不需要去使用for循环，直接进行条件判断就好了

• 如果左括号的数量小于n，我们就往str中加上一个左括号，然后进行回溯，回溯结束后，不要忘记删除加入str的括号。

• 如果右括号的数量小于左括号的数量，我们就往str中加入一个右括号，然后进行回溯，回溯结束后，别忘记加入str中的括号

整个回溯的逻辑就是这样，下面请看具体代码：

class Solution {
public:// 左括号的数量不能大于 n 。// 右括号的数量不能大于当前已经添加的左括号的数量。vector<string> generateParenthesis(int n) {vector<string> result;string str;backtracking(0,0,str,result,n);return result;}void backtracking(int left,int right,string& str,vector<string>& result,int n){if(str.size() == 2*n){result.push_back(str);return ;}if(left < n){str += "(";backtracking(left+1,right,str,result,n);str.pop_back();}if(left > right ){  str += ")";backtracking(left,right+1,str,result,n);str.pop_back();}}
};

复杂度分析

时间复杂度：

在这个问题中，我们需要生成所有可能的合法括号组合。对于每个位置，我们可以选择添加左括号或右括号（当然要满足条件）。因此，在最坏的情况下，时间复杂度可以看作是 O(2^(2n)/√n)。这个估计来自于卡特兰数（Catalan number），它是解决这类问题（括号生成）的通常方法。对于 n 对括号，卡特兰数 C(n) = (1/(n+1))(2n)!/((n!)(n+1)!))。卡特兰数增长的速度相当于 O(4^n/(n*√n))。

空间复杂度：

空间复杂度主要取决于两个方面：递归深度和结果列表。递归深度最多为 2n，因为每个递归调用都会消耗 O(1) 的栈空间，所以递归调用栈的空间复杂度为 O(2n)。结果列表中包含 C(n) 个元素，每个元素是一个长度为 2n 的字符串。因此，结果列表的空间复杂度为 O(C(n) * 2n) = O(4^n/√n * 2n)。

总结

这道题可以归类为回溯算法可以解决一类问题中的排列问题。但这和普通的排列问题还不一样，这是一种特殊的排列问题。因为左括号的数量要始终要大于右括号，有了限制条件后，就和一般的排列问题不一样了。

还是很有意思的，这一道题。这道题用回溯算法已经算是最优解了

这道题的解决方案与卡特兰数相关，它的时间复杂度和空间复杂度都与卡特兰数有关。

在这种情况下，尝试寻找一种更好的方法并不容易。因为我们需要生成所有可能的合法括号组合，所以无论如何，我们都需要遍历这个解空间。回溯算法在这里表现得非常好，因为它能够在满足约束条件的情况下生成所有可能的解。而且，它在遍历解空间时非常高效，因为它可以在不满足条件的情况下立即剪枝。

当然，这并不意味着没有其他方法可以解决这个问题。例如，你可以尝试动态规划，但这种方法的实现会更加复杂，而且在这种情况下它的性能可能不如回溯算法。所以，对于这道题，回溯方法已经是很好的解决方案了。