LeetCode 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:

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

public List<String> generateParenthesis(int n) {
    char[] pars = new char[n*2];
    List<String> result = new ArrayList<>();
    generate(result, n, n, pars, 0);
    return result;
}

private void generate(List<String> result, int l, int r, char[] pars, int index) {
    if(l>r) return;
    if(r==0) {
        result.add(new String(pars));
        return;
    }
    if(l>0) {
        pars[index] = '(';
        generate(result, l-1, r, pars, index+1);
    }
    if(r>l) {
        pars[index] = ')';
        generate(result, l, r-1, pars, index+1);
    }
}

 

C++的做法略有不同，C的char数组元素个数必需为2n+1个，因为最后一个元素用来存储终止符 ' \0 '。

vector<string> generateParenthesis(int n) {
    vector<string> result;
    char p[n*2+1];
    p[n*2] = '\0';
    generate(result, p, n, n, 0);
    return result;
}

void generate(vector<string>& result, char* p, int l, int r, int i) {
    if(l > r) return;
    if(r == 0) {
        result.push_back(string(p));
        return;
    }
    if(l > 0) {
        p[i] = '(';
        generate(result, p, l-1, r, i+1);
    }
    if(l < r) {
        p[i] = ')';
        generate(result, p, l, r-1, i+1);
    }
}