WEI-CHENG CHEN

說明

題目跟你說要擠兌括弧，然後去作排列組合

解法

遞迴長相

          ""
         /   \
       "("   不合法 (右括號不能先出現)
      /   \
   "(("    "()"
  /   \   /   \
"(((" "(()" "()" "(())"

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string s = "";
        backtracking(ans, s, n, 0, 0);
        return ans;
    }

    void backtracking(vector<string> &ans, string s, int n, int left, int right){
        // 終止條件
        if(left<right) return;
        else if(left==n && right==n){
            ans.push_back(s);
            return;
        }
        // 繼續地回
        // 要遞迴左括弧
        if(left<n){
            backtracking(ans, s+"(", n, left+1, right);
        }
        // 要遞迴右括弧
        if(right<left){
            backtracking(ans, s+")", n, left, right+1);
        }
    }
};