22. Generate Parentheses

題目描述：

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:

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

解題思路：

這個是用迭代方法，當左括號和又括號的個數相同且等于輸入n時將此時的字符串存入vector中。

這題是用回溯方法估計會更好些。

代碼：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        generate(n, 0, 0, "", ret);
        return ret;
    }
    void generate(int n, int numl, int numr, string str, vector<string>& ret) {
        if (numl < numr || numl > n || numr > n)
            return;
        if (numl == n && numr == n)
            ret.push_back(str);
        if (numl < n) {
            generate(n, numl+1, numr, str+"(", ret);
            generate(n, numl, numr+1, str+")", ret);
        } else {
            generate(n, numl, numr+1, str+")", ret);
        }
    }
};

?