> 文章列表 > 《程序员面试金典(第6版)》面试题 08.09. 括号(回溯算法,特殊的排列问题,C++)

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

《程序员面试金典(第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)。

总结

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

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

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

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

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