TOP101题解 | BM60#括号生成#

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/***********************************************************************************************************
 * @param n int整型 括号总个数 
 * @param sum int整型 解的个数 
 * @param left int整型 左括号已用个数 
 * @param right int整型 右括号已用个数
 * @param result 结果数组 
 * @param path 解的组合 
 * @param cur_index 当前下标 
 * @brief 递归调用选取括号数
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 ********************************************************************************************************/
void Parenthesis(int n, int left, int right, char** result, char* path, int* returnSize,int cur_index)
{
    if(cur_index == 2 * n)
    {
        path[2 * n] = '\0';
        char* temp = (char*)malloc( (2 * n + 1) * sizeof(char));
        strcpy(temp, path);
 
        result[*returnSize] = temp;
        (*returnSize)++;

        return;
    }
    else 
    {
        /*左括号合法*/
        if(left < n)
        {
            path[cur_index] = '(';
            Parenthesis( n, left + 1,  right,  result,  path, returnSize, cur_index + 1);
        }
        /*右括号一定要比左括号多*/
        if(right < left )
        {
            path[cur_index] = ')';
            Parenthesis( n, left,  right + 1,  result,  path, returnSize, cur_index + 1);
        }
    }
}

/***********************************************************************************************************
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.27
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * 
 * @param n int整型 
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数***********************************************************************************************************/
char** generateParenthesis(int n, int* returnSize )
{
    // write code here
    char** result = (char**)malloc( 1000 * sizeof(char*) );/*结果数组*/

    char path[2 * n + 1];/*路径数组,记录一个解*/

    *returnSize = 0;

    Parenthesis(n, 0, 0, result, path, returnSize, 0);/*递归求解*/
    
    return result;
}