22. Generate Parentheses
1.問題

2.想法
提問
function header, parameter
test input
說明想法
可以看成"(", ")"的排列組合, 使用ray tracking, 並限制長度個數 (用減的)
但是"("一定要出現在")"之前, 否則return
測試計算複雜度: O(2 ^ n)
3.程式碼
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
generate(n, n, "", res);
return res;
}
private:
void generate(int left, int right, string out, vector<string>& res) {
if (left < right) {
return;
}
if (left == 0 && right == 0){
res.push_back(out);
return;
}
if (left > 0) {
generate(left - 1, right, "(" + out, res);
}
if (right > 0) {
generate(left, right - 1, ")" + out, res);
}
}
};
Last updated