。

设计一种算法#xff0c;打印n对括号的所有合法的#xff08;例如#xff0c;开闭一一对应#xff09;组合。

例如#xff0c;给出

括号。

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

例如给出

[((())),(()()),(())(),()(()),()()()

]解题思路与代码

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

写一道回溯算法的题的时候一般是先去想这算法该如何返回。

那么当str的长度等于2倍的n时就该返回了把str存入result后返回

之后我们就要去做判断了。

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

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

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

class

右括号的数量不能大于当前已经添加的左括号的数量。

vectorstring

{vectorstring

str;backtracking(0,0,str,result,n);return

result;}void

2*n){result.push_back(str);return

;}if(left

(;backtracking(left1,right,str,result,n);str.pop_back();}if(left

right

);backtracking(left,right1,str,result,n);str.pop_back();}}

};复杂度分析

在这个问题中我们需要生成所有可能的合法括号组合。

对于每个位置我们可以选择添加左括号或右括号当然要满足条件。

因此在最坏的情况下时间复杂度可以看作是

O(2^(2n)/√n)。

这个估计来自于卡特兰数Catalan

对括号卡特兰数

(1/(n1))(2n)!/((n!)(n1)!))。

卡特兰数增长的速度相当于

空间复杂度

空间复杂度主要取决于两个方面递归深度和结果列表。

递归深度最多为

2n因为每个递归调用都会消耗

这道题可以归类为回溯算法可以解决一类问题中的排列问题。

但这和普通的排列问题还不一样这是一种特殊的排列问题。

因为左括号的数量要始终要大于右括号有了限制条件后就和一般的排列问题不一样了。

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

在这种情况下尝试寻找一种更好的方法并不容易。

因为我们需要生成所有可能的合法括号组合所以无论如何我们都需要遍历这个解空间。

回溯算法在这里表现得非常好因为它能够在满足约束条件的情况下生成所有可能的解。

而且它在遍历解空间时非常高效因为它可以在不满足条件的情况下立即剪枝。

当然这并不意味着没有其他方法可以解决这个问题。

例如你可以尝试动态规划但这种方法的实现会更加复杂而且在这种情况下它的性能可能不如回溯算法。

所以对于这道题回溯方法已经是很好的解决方案了。