leeched 22. 括号生成 最佳解法

題目描述： 數字 n 代表生成括号的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括号組合。

示例 1：

輸入：n = 3

輸出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

輸入：n = 1

輸出：["()"]

提示：

1 <= n <= 8

通過次數268,900送出次數348,796

class Solution {
public:
    vector<string> ret;
    void search(int k,string str,int n){
        if(k == 0 && n == 0){
            ret.push_back(str);
            return;
        }
        if(n>0)search(k+1,str+"(",n-1);
        if(k>0)search(k-1,str+")",n);
    }

    vector<string> generateParenthesis(int n) {
        if(n<1) return {};
        int k = 0;
        search(k,"",n);
        return ret;
    }
};
           

思路，首先讀題我們可以知道。n為可添加左括号數量。那麼在操作上，可以配對一個右括号或者繼續添加左括号，也就是可加可不加的選擇問題。

那麼整個題解法就是樹的深度周遊，左右節點就是添加或者不添加。

過程中抽象了括弧'(' , ')'的存儲過程，用k代表stack棧剩餘左括号的數量。

是以n是左括号可添加總數，k是左括号剩餘數量。

當兩者都為零時，則說明已經完成括号比對輸入，直接儲存目前結果。