題目描述: 數字 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是左括号剩餘數量。
當兩者都為零時,則說明已經完成括号比對輸入,直接儲存目前結果。