22. Generate Parentheses，生成合法的括号组合

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        s = set()
        s.add('()')
        for i in range(n-1):
            p = set()
            for it in s:
                for j in range(len(it)):
                    p.add(it[:j]+'()'+it[j:])
            s = p
        return list(s)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def _backtrack(comb, nlp, nrp):
            if nlp == nrp == 0:
                yield comb
                return
            if nlp:
                yield from _backtrack(comb+'(', nlp-1, nrp)
            if nrp > nlp:
                yield from _backtrack(comb+')', nlp, nrp-1)
        return list(_backtrack('',n,n))

class Solution {
    vector<string> r;
    void backtrack(string t, int left, int right){
        if(left==0 && right==0){
            r.push_back(t);   
            return;
        }
        if(left > 0)
            backtrack(t+'(', left-1, right);
        if(right > left)
            backtrack(t+')', left, right-1);
        return;
    }
public:
    vector<string> generateParenthesis(int n) {
        r.clear();
        backtrack("", n, n);
        return r;
    }
};

static char **r;
static int ridx;

static void _backtrack(const int size, char *it, int idx, int nlp, int nrp){
    if(nlp==0 && nrp==0){
        if(ridx%64 == 0)
            r = realloc(r, sizeof(char*)*(ridx/64+1)*64);
        r[ridx] = malloc(size);
        memcpy(r[ridx], it, size);
        ++ridx;
        return;
    }
    if(nlp > 0){
        it[idx] = '(';
        _backtrack(size, it, idx+1, nlp-1, nrp);
    }
    if(nrp > nlp){
        it[idx] = ')';
        _backtrack(size, it, idx+1, nlp, nrp-1);
    }
    return;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** generateParenthesis(int n, int* returnSize){
    int size = n*2 + 1;
    char *it = malloc(size);
    it[size-1] = 0;
    r = NULL;
    ridx = 0;
    _backtrack(size, it, 0, n, n);
    *returnSize = ridx;
    return r;
}