###### tags: `LeetCode` `Recursion` `String` `Medium`
# LeetCode #22 [Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)
### (Medium)

數字 n 代表生成括號的對數，請你設計一個函數，用於能夠生成所有可能的並且 有效的 括號組合。

有效括號組合需滿足：左括號必須以正確的順序閉合。

---

這題的重點在於, 如何做出有效括號-只要保持左括號數量不小於右括號即可。

終止條件:
* 右括號數量大於左括號數量, 失敗-直接返回
* 左右括號數量皆等於要求數量, 此為成功條件, 將字串存入答案數組中, 然後返回
* 左或右括號的數量超過給定數, 失敗-直接返回

程式碼中的tmp使用參考與否並不影響正確性, 若使用參考, 需要搭配左(右)括號的插入與彈出(因為所有的字串共用同一個變數), 好處是節省記憶體空間; 不使用參考就不用那麼麻煩, 每次遞迴傳入舊字串加上左(右)括號即可, 但每次呼叫遞迴都需要額外記憶體空間儲存新字串。

---

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string tmp="";
        vector<string> ans;
        dfs(n, n, tmp, ans);
        return ans;
    }
    void dfs(int left, int right, string& tmp, vector<string>& ans){
        if(left==-1||right==-1)return;
        if(right<left)return;
        if(!left&&!right){
            ans.push_back(tmp);
            return;
        }
        tmp+='(';
        dfs(left-1, right, tmp, ans);
        tmp.pop_back();
        tmp+=')';
        dfs(left, right-1, tmp, ans);
        tmp.pop_back();
    }
};