C语言-详细讲解-给定数字n，生成共有n个括号的所有正确的形式

1.题目要求

(语言: C)给定一个数字n，生成共有n个括号的所有正确的形式
例如n=3时生成的括号为
"((()))", "(()())", "(())()", "()(())", "()()()"
输入输出格式为
printf("Please input the number\n");
scanf("%d");
printf("values are %d\n");
for ( )
{
        printf("%s\n");
}
函数原型为
char** generateParenthesis(int n, int* returnSize) 
注：不考虑非法输入的情况，输入的必须是正整数，且不超过10，数目太大程序运行太慢。
程序运行示例
Please input the number
3
values are 5
((()))
(()())
(())()
()(())
()()()

2.代码实现 

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

void generate(char** result, int* returnSize, char* current, int left, int right, int index, int n) {
    if (left == 0 && right == 0) {
        result[*returnSize] = (char*)malloc(sizeof(char) * (n * 2 + 1));
        strcpy(result[*returnSize], current);
        (*returnSize)++;
        return;
    }
    if (left > 0) {
        current[index] = '(';
        generate(result, returnSize, current, left - 1, right, index + 1, n);
    }
    if (right > left) {
        current[index] = ')';
        generate(result, returnSize, current, left, right - 1, index + 1, n);
    }
}

char** generateParenthesis(int n, int* returnSize) {
    char** result = (char**)malloc(sizeof(char*) * 1000);
    char* current = (char*)malloc(sizeof(char) * (n * 2 + 1));
    current[n * 2] = '\0';
    *returnSize = 0;
    generate(result, returnSize, current, n, n, 0, n);
    free(current);  // 释放 current 分配的内存
    return result;
}

int main() {
    int n;
    printf("Please input the number\n");
    scanf("%d", &n);
    int returnSize;
    char** result = generateParenthesis(n, &returnSize);
    printf("values are %d\n", returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", result[i]);
        free(result[i]);  // 释放 result 中每个元素所指向的内存
    }
    free(result);  // 释放 result 数组本身
    return 0;
}

3.代码详解 

1.知识点：此题需灵活运用递归和指针，还涉及到了动态内存管理。

2.generate函数

• 函数参数：
  • char** result：一个指向字符指针的指针，用于存储生成的括号组合。
  • int* returnSize：一个指向整数的指针，用于记录生成的括号组合的数量。
  • char* current：一个字符数组，用于存储当前正在生成的括号组合。
  • int left：表示还可以使用的左括号的数量。
  • int right：表示还可以使用的右括号的数量。
  • int index：表示当前正在生成括号的位置。
  • int n：表示总的括号对数。
• 递归逻辑：
  • 当 left 和 right 都为 0 时，说明已经生成了一个合法的括号组合。使用 malloc 为该组合分配内存，使用 strcpy 将 current 复制到 result[*returnSize] 中，并增加 *returnSize 的值。
  • 如果 left 大于 0，将 ( 放入 current[index] 位置，并递归调用 generate 函数，同时减少 left 的数量，增加 index 的位置。
  • 如果 right 大于 left，将 ) 放入 current[index] 位置，并递归调用 generate 函数，同时减少 right 的数量，增加 index 的位置。

3.递归思想

• 本题使用递归算法来生成括号组合。
• 从空字符串开始，在每个位置上可以选择添加 ( 或 )。
• 递归的终止条件是 left 和 right 都为 0，即已经使用完所有的括号。
• 为保证括号组合合法，添加左括号的条件是 left > 0，添加右括号的条件是 right > left，这是因为在任何时刻，左括号的数量不能小于右括号的数量。