題目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

分析

排列組合題首先考慮遞歸，把f(n)分成三種情況：{"("+f(n-1)+")", "()"+f(n-1), f(n-1)+"()"}，但是發(fā)現(xiàn)這樣漏掉了一些情況，比如n=4時的"(())(())"。
碰壁之后從狀態(tài)空間考慮。從左往右考慮每個字符的取法。由于括號的總數(shù)是不變的，當(dāng)左括號有剩余時，隨時都可以放置左括號，而左括號的數(shù)目達(dá)到了之后就必須放右括號。而右括號放置時必須保證其之前的左括號數(shù)目大于目前的右括號數(shù)目。這樣就把狀態(tài)空間表示成了樹的形式。而由于樹的深度是一定的，為2*n，所以考慮用遞歸實現(xiàn)其遍歷。

實現(xiàn)

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n==0) return {};
        return solve(2*n, 0, n);
    }
private:
    vector<string> solve(int layer, int ul, int ll){
        if(layer==1) return {")"};
        vector<string> ans;
        vector<string> tmp;
        if(ul<=0){
            tmp = solve(layer-1, ul+1, ll-1);
            for(auto s: tmp){
                ans.push_back("("+s);
            }
        }
        else if(ll<=0){
            tmp = solve(layer-1, ul-1, ll);
            for(auto s: tmp){
                ans.push_back(")"+s);
            }
        }
        else{
            tmp = solve(layer-1, ul+1, ll-1);
            for(auto s: tmp){
                ans.push_back("("+s);
            }
            tmp = solve(layer-1, ul-1, ll);
            for(auto s: tmp){
                ans.push_back(")"+s);
            }
        }
        return ans;
    }
};

思考

雖然我這種解法能行，但是看了別人的解法之后覺得實在是太復(fù)雜了，而且不是很快。由于看到的方法實在太優(yōu)美了，所以忍不住貼上來。
其中的思想總結(jié)下就是：

• 使用一個字符串參數(shù)表示之前字符的排列信息
• 引用傳參，且當(dāng)?shù)竭_(dá)末尾時再push_back結(jié)果
• 減少不必要的if else。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        addParenthesis(ans, "", n, 0);
        return ans;
    }
    
    void addParenthesis(vector<string>& ans, string s, int n, int m) {
        if (n == 0 && m == 0)
            ans.push_back(s);
        
        if (n > 0) addParenthesis(ans, s+"(", n-1, m+1);
        if (m > 0) addParenthesis(ans, s+")", n, m-1);
    }
};