天天看點

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是左括号剩餘數量。

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

繼續閱讀