以leetcode22題為例

題目分析：

給一個數字n，返回合法的所有的括號組合?

算法原理分析：

你可以先考慮如何不重不漏的羅列所有的括號組合

清楚什么是有效的括號組合？？？

1.所有的左括號的數量等于右括號的數量

2.從頭開始的所有子串，左括號的數量>=右括號的數量（注意我說的是子串，而且是從頭開始）

決策樹的畫法如下：

你每填一個位置的時候都要想一想是否符合有效的括號組合的兩條性質

不符合的就可以剪枝

設計代碼：

1.全局變量：我們需要返回一個字符串數組，所以需要一個ret去統計每個葉子結點

? ? ? ? ? ? ? ? ? ? ?我們需要一個path去統計是否到了葉子結點，如果到了就放到ret中

? ? ? ? ? ? ? ? ? ? 我在設計剪枝的時候發現問題，我需要知道左括號和右括號的數量

? ? ? ? ? ? ? ? ? ? 所以我設計一個全局變量left和right分別表示左右括號的數量

2.dfs函數：關心每一個結點所做的事情，就是枚舉左括號和右括號看哪一個符合，然后是否加到? ? ? ? ? ? ? ? ? ? ? ?path的后面

3.細節：回溯：回上一層只需要path.pop_back()即可,還要把left和right里面的括號數量處理

? ? ? ? ? ? ? 剪枝：這里我們選擇只關心合法的分支

? ? ? ? ? ? ? ? ? ? ? ? ?左括號的選擇：只要還可以選擇就一直選（left<n/2）

? ? ? ? ? ? ? ? ? ? ? ? ?右括號的選擇：只要還可以選&&left>right

代碼編寫：

注意我的dfs函數設計的n是左括號和右括號的數量和

所有我傳參的時候是n*2；?