[LeetCode] 22. generate parentheses

• Problem: 給定括號個數, 產生合法的括號排列組合
• Solution:
• 以 recursive 方式來解決
• 當下考慮的是, 還要加入幾個左括號及幾個右括號
• 終止條件: 左右括號都加完了
• 當前條件: 左括號沒有限制, 右括號則需有對應的左括號先加入了才行
• Note: 注意邊際條件 leftCount > 0
• Code

class Solution {
public:
    // recursive solve this problem
    static void genParenthesis(vector &result, string s, int leftCount, int rightCount) {
        // when append done, add string to vector
        if (0 == leftCount && 0 == rightCount)
            result.push_back(s);

        // no matter where position, if leftCount > 0, you can add it
        if (leftCount > 0) 
            genParenthesis(result, s + "(", leftCount - 1, rightCount); 

        // you can append right parenthesis only when rightCount > leftCount
        if (leftCount < rightCount)
            genParenthesis(result, s + ")", leftCount, rightCount - 1);
    }
    
    vector generateParenthesis(int n) {
        vector result;
        genParenthesis(result, "", n, n);
        return result;
    }
};