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: "((()))", "(()())", "(())()", "()(())", "()()()" http://leetcode.com/onlinejudge

leetcode_generate_parentheses.cpp

class Solution {
public:
    void dfs(vector<string>& ret, char* buf, int n, int id, int cnt1, int cnt2) {
        if (id == 2 * n) {
            buf[id] = 0;
            ret.push_back(buf);
            return;
        }
        if (cnt1 < n) {
            buf[id] = '(';
            dfs(ret, buf, n, id + 1, cnt1 + 1, cnt2);
        }
        if (cnt1 > cnt2) {
            buf[id] = ')';
            dfs(ret, buf, n, id + 1, cnt1, cnt2 + 1);
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        if (n == 0)
            return ret;
        char buf[1024];
        dfs(ret, buf, n, 0, 0, 0);
        return ret;
    }
};