题解 | #括号生成#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 */

void DFS(int left, int right, char **ret, char *str, int n, int* returnSize) {
    // 如果左右括号的数量都是n，那么表示组合结束，需要退出
    if(left == n && right == n) {
        // 申请内存长度为2n
        ret[(*returnSize)] = (char*)malloc(sizeof(char) * 2 * n);
        // 将str复制到返回的结果中
        strncpy(ret[(*returnSize)], str, 2 * n);
        (*returnSize)++;
        return;
    }
    // 如果左括号还没有用完，继续增加括号
    if(left < n) {
        str[left + right] = '(';
        DFS(left + 1, right, ret, str, n, returnSize);
    }
    // 如果右括号没有用完，并且个数小于左括号的个数，（如果大于等于左括号的个数，组合就不合法了）
    if(right < n && right < left) {
        str[left + right] = ')';
        DFS(left, right + 1, ret, str, n, returnSize);
    }
}



char** generateParenthesis(int n, int* returnSize ) {
    // write code here
    char **ret = (char**)malloc(sizeof(char*) * 2000);
    *returnSize = 0;
    char *str = (char*)malloc(sizeof(char) * 2 * n);
    DFS(0,0,ret,str,n,returnSize);
    return ret;
}