題目描述

括號(hào)。設(shè)計(jì)一種算法，打印n對(duì)括號(hào)的所有合法的（例如，開(kāi)閉一一對(duì)應(yīng)）組合。

說(shuō)明：解集不能包含重復(fù)的子集。

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

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

解題思路與代碼

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

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

方法一 ： 回溯法

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

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

• 寫(xiě)一道回溯算法的題的時(shí)候，一般是先去想，這算法該如何返回。那么當(dāng)str的長(zhǎng)度等于2倍的n時(shí)，就該返回了，把str存入result后返回

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

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

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

整個(gè)回溯的邏輯就是這樣，下面請(qǐng)看具體代碼：

class Solution {
public:// 左括號(hào)的數(shù)量不能大于 n 。// 右括號(hào)的數(shù)量不能大于當(dāng)前已經(jīng)添加的左括號(hào)的數(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();}}
};

復(fù)雜度分析

時(shí)間復(fù)雜度：

在這個(gè)問(wèn)題中，我們需要生成所有可能的合法括號(hào)組合。對(duì)于每個(gè)位置，我們可以選擇添加左括號(hào)或右括號(hào)（當(dāng)然要滿(mǎn)足條件）。因此，在最壞的情況下，時(shí)間復(fù)雜度可以看作是 O(2^(2n)/√n)。這個(gè)估計(jì)來(lái)自于卡特蘭數(shù)（Catalan number），它是解決這類(lèi)問(wèn)題（括號(hào)生成）的通常方法。對(duì)于 n 對(duì)括號(hào)，卡特蘭數(shù) C(n) = (1/(n+1))(2n)!/((n!)(n+1)!))。卡特蘭數(shù)增長(zhǎng)的速度相當(dāng)于 O(4^n/(n*√n))。

空間復(fù)雜度：

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

總結(jié)

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

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

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

在這種情況下，嘗試尋找一種更好的方法并不容易。因?yàn)槲覀冃枰伤锌赡艿暮戏ɡㄌ?hào)組合，所以無(wú)論如何，我們都需要遍歷這個(gè)解空間。回溯算法在這里表現(xiàn)得非常好，因?yàn)樗軌蛟跐M(mǎn)足約束條件的情況下生成所有可能的解。而且，它在遍歷解空間時(shí)非常高效，因?yàn)樗梢栽诓粷M(mǎn)足條件的情況下立即剪枝。

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