力扣22题：括号生成—C实现—回溯—卡塔兰数

力扣第22题：括号生成

题目描述

给定 n 对括号，写一个函数来生成所有由 n 对括号组成的有效组合。

示例

输入：n = 3
输出：["((()))", "(()())", "(())()", "()(())", "()()()"]

解题思路

使用回溯算法生成所有可能的括号组合。我们需要维护两个计数器来追踪当前使用的左括号和右括号数量，确保在构建过程中生成的组合是有效的。

生成的括号组合数其实是卡塔兰数，随 n 的增大呈指数级增长。因此，分配内存时需要根据实际情况进行计算。根据卡塔兰数的性质，生成的有效括号组合数为 $C (2 n, n) / (n + 1)$ ，可以计算出准确的内存需求。我们可以通过在 result 中分配足够的空间来避免溢出。

代码实现

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

// 递归生成括号组合的辅助函数
void generateParenthesisHelper(char **result, int *returnSize, char *current, int left, int right, int n) {
    if (left == n && right == n) {
        // 保存当前生成的组合
        result[*returnSize] = (char *)malloc((2 * n + 1) * sizeof(char));
        strcpy(result[*returnSize], current);
        (*returnSize)++;
        return;
    }

    if (left < n) {
        // 添加左括号
        current[left + right] = '(';
        generateParenthesisHelper(result, returnSize, current, left + 1, right, n);
    }
    
    if (right < left) {
        // 添加右括号
        current[left + right] = ')';
        generateParenthesisHelper(result, returnSize, current, left, right + 1, n);
    }
}

// 计算卡塔兰数，用于估算括号组合数
int catalanNumber(int n) {
    long long result = 1;
    for (int i = 0; i < n; i++) {
        result = result * (2 * n - i) / (i + 1);
    }
    return result / (n + 1);
}

// 主函数，生成所有有效的括号组合
char **generateParenthesis(int n, int *returnSize) {
    *returnSize = 0;

    // 估计组合数（卡塔兰数）
    int maxSize = catalanNumber(n);
    
    char **result = (char **)malloc(maxSize * sizeof(char *));
    char *current = (char *)malloc((2 * n + 1) * sizeof(char));
    current[2 * n] = '\0';  // 结果字符串以'\0'结尾
    
    // 调用递归函数
    generateParenthesisHelper(result, returnSize, current, 0, 0, n);
    
    free(current);
    return result;
}

// 测试程序
int main() {
    int n = 5;
    int returnSize;
    char **result = generateParenthesis(n, &returnSize);
    
    // 输出所有生成的括号组合
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", result[i]);
        free(result[i]);  // 释放每个字符串的内存
    }
    free(result);  // 释放结果数组的内存
    
    return 0;
}

代码详解

generateParenthesisHelper 函数：
- 参数：
  - result：保存生成的有效括号组合。
  - returnSize：当前生成组合的数量。
  - current：当前生成的括号组合。
  - left：已使用的左括号数量。
  - right：已使用的右括号数量。
  - n：总的括号对数。
- 逻辑：
  - 当左右括号数量均达到 n 时，将当前组合保存到结果中。
  - 如果左括号数量小于 n，则可以添加左括号并递归。
  - 如果右括号数量小于左括号数量，则可以添加右括号并递归。
catalanNumber 函数：
- 用于计算卡塔兰数，以估计括号组合的数量。
- 使用动态规划方法计算。
generateParenthesis 主函数：
- 初始化结果数组，并调用辅助函数生成组合。
- 使用 malloc 动态分配内存，并在使用后释放。

回溯过程示意图

回溯过程中，我们会记录当前的组合和左右括号的使用情况。以下是一个示意图，以 n = 3 为例。

过程解释

从空字符串开始，每一步选择添加左括号 ( 或右括号 )。
每当选择添加左括号，计数器 left 加 1；添加右括号时，计数器 right 加 1。
递归继续，直到左右括号的数量均达到 n，此时保存当前组合。

结论

通过回溯算法，可以有效生成所有有效的括号组合，解决问题的复杂度随着 n 增加而呈指数增长。在实际应用中，这种方法对于生成组合问题非常有效且直观。

秒客网