題目描述

括號。設(shè)計一種算法，打印n對括號的所有合法的（例如，開閉一一對應(yīng)）組合。

說明：解集不能包含重復的子集。

例如，給出 n = 3，生成結(jié)果為：

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

解題思路與代碼

這道題抽象總結(jié)出來，就只有兩條規(guī)則，分別是：

• 左括號的數(shù)量不能多于n
• 右括號的數(shù)量不能多于左括號

方法一 ： 回溯法

這道題我看了一下，比較適合用回溯法去解決。

• 我們需要一個輔助函數(shù)backtracking，它一共需要設(shè)置這么幾個參數(shù)，分別是左括號的數(shù)量left，右括號的時候，right，n的大小n，存儲結(jié)果集的向量result，一個string用來放括號字符str，共5個參數(shù)。

• 寫一道回溯算法的題的時候，一般是先去想，這算法該如何返回。那么當str的長度等于2倍的n時，就該返回了，把str存入result后返回

• 之后我們就要去做判斷了。這道題和一般的回溯算法不一樣，我們這里不需要去使用for循環(huán)，直接進行條件判斷就好了

• 如果左括號的數(shù)量小于n，我們就往str中加上一個左括號，然后進行回溯，回溯結(jié)束后，不要忘記刪除加入str的括號。

• 如果右括號的數(shù)量小于左括號的數(shù)量，我們就往str中加入一個右括號，然后進行回溯，回溯結(jié)束后，別忘記加入str中的括號

整個回溯的邏輯就是這樣，下面請看具體代碼：

class Solution {
public:// 左括號的數(shù)量不能大于 n 。// 右括號的數(shù)量不能大于當前已經(jīng)添加的左括號的數(shù)量。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)。這個估計來自于卡特蘭數(shù)（Catalan number），它是解決這類問題（括號生成）的通常方法。對于 n 對括號，卡特蘭數(shù) C(n) = (1/(n+1))(2n)!/((n!)(n+1)!))?？ㄌ靥m數(shù)增長的速度相當于 O(4^n/(n*√n))。

空間復雜度：

空間復雜度主要取決于兩個方面：遞歸深度和結(jié)果列表。遞歸深度最多為 2n，因為每個遞歸調(diào)用都會消耗 O(1) 的?？臻g，所以遞歸調(diào)用棧的空間復雜度為 O(2n)。結(jié)果列表中包含 C(n) 個元素，每個元素是一個長度為 2n 的字符串。因此，結(jié)果列表的空間復雜度為 O(C(n) * 2n) = O(4^n/√n * 2n)。

總結(jié)

這道題可以歸類為回溯算法可以解決一類問題中的排列問題。但這和普通的排列問題還不一樣，這是一種特殊的排列問題。因為左括號的數(shù)量要始終要大于右括號，有了限制條件后，就和一般的排列問題不一樣了。

還是很有意思的，這一道題。這道題用回溯算法已經(jīng)算是最優(yōu)解了

這道題的解決方案與卡特蘭數(shù)相關(guān)，它的時間復雜度和空間復雜度都與卡特蘭數(shù)有關(guān)。

在這種情況下，嘗試尋找一種更好的方法并不容易。因為我們需要生成所有可能的合法括號組合，所以無論如何，我們都需要遍歷這個解空間。回溯算法在這里表現(xiàn)得非常好，因為它能夠在滿足約束條件的情況下生成所有可能的解。而且，它在遍歷解空間時非常高效，因為它可以在不滿足條件的情況下立即剪枝。

當然，這并不意味著沒有其他方法可以解決這個問題。例如，你可以嘗試動態(tài)規(guī)劃，但這種方法的實現(xiàn)會更加復雜，而且在這種情況下它的性能可能不如回溯算法。所以，對于這道題，回溯方法已經(jīng)是很好的解決方案了。