022 - Generate Parentheses

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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Hide Tags
Backtracking String
Hide Similar Problems
(M) Letter Combinations of a Phone Number (E) Valid Parentheses

虽然跟电话键盘那题相似，但还是有些不同的：
第一个只能是左括号；
左括号的数量始终要比右括号多；
如果左右括号各剩一个，那就到头了，只能多加一个 "()"；
如果左括号剩余零个，也到头了，只能把剩下的右括号全加上；
其他情况就可以左右都选，进行组合。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> rst;
        string buf="";
       
        if(n)
        {
            buf += '(';            build(n-1, n, buf, rst);
        }
        return rst;
    }
    void build(int ln, int rn, string& buf, vector<string>& rst)
    {
        //ending part I: only one possibility: add "()"        if(1==ln && 1==rn)
            rst.push_back(buf + "()");
        //ending part II: all '(' are used, can only finish with all ')'        else if(0==ln)
        {
            string tmp="";
            while(rn)
                tmp += ')', rn--;
            rst.push_back(buf+tmp);
        }
        //between first and ending part        else
        {
            //cannot put more ')' than all existing '('            if(ln<=rn)            {
                //try add '(' and move further                if(ln)
                {
                    buf.push_back('(');
                    build(ln-1, rn, buf, rst);
                    buf.pop_back();
                }
                //try add ')' and move further                if(rn)
                {
                    buf.push_back(')');
                    build(ln, rn-1, buf, rst);
                    buf.pop_back();
                }
            }                   
        }
        return;
    }
};
0 ms.

这个写得挺简练：左边小于总数就可以加左边，右边小于左边就可以加右边。