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:

"((()))", "(()())", "(())()", "()(())", "()()()"

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string item;
        traverse(result, item, n, n);
        return result;
    }

    void traverse(vector<string> &res, string &item, int left, int right) {
        if (!left && !right)
                return res.push_back(item);

        if (right < left)
                return;

        if (left) {
                item.push_back('(');
                traverse(res, item, left-1, right);
                item.pop_back(); // c++ 11
        }

        if (right) {
                item.push_back(')');
                traverse(res, item, left, right-1);
                item.pop_back(); // c++ 11
        }
    }
};

在leetcode上的执行时间为4ms。

此算法的关键点是，在构造子串中，确保左括号的数量必须大于或者等于右括号。

Generate Parentheses -- leetcode