C 语言实现括号有效组合生成算法：代码详解及时间复杂度分析

使用 C 语言解决括号有效组合生成问题：代码详解及时间复杂度分析

问题描述： 编写一个方法，打印 n 对括号的全部有效组合（即左右括号正确匹配）。例如当 n=3 时，有效组合为'(())()', '(()())', '(())()', '()(())', '()()()'。

a. 问题分析： 本问题要求打印出 n 对括号的所有有效组合，即左右括号必须正确匹配。

b. 解题思路分析： 我们可以使用递归的方法来解决这个问题。递归函数的参数包括当前生成的字符串、剩余左括号的数量和剩余右括号的数量。每次递归调用时，我们有两种选择：添加一个左括号或添加一个右括号。但是需要注意的是，添加一个左括号的条件是剩余左括号的数量大于 0，添加一个右括号的条件是剩余右括号的数量大于剩余左括号的数量。当剩余左括号和右括号的数量都为 0 时，即生成了一个有效组合，将其添加到结果集中。

c. 完整的代码注释：

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

void generateParenthesisHelper(char* str, int left, int right, int index, char** result, int* returnSize) {
    // 如果剩余左括号和右括号的数量都为 0，即生成了一个有效组合，将其添加到结果集中
    if (left == 0 && right == 0) {
        result[*returnSize] = strdup(str); // 将生成的字符串拷贝到结果集中
        (*returnSize)++; // 结果集大小加 1
        return;
    }
    
    // 如果剩余左括号的数量大于 0，则可以添加一个左括号
    if (left > 0) {
        str[index] = '('; // 添加左括号
        generateParenthesisHelper(str, left - 1, right, index + 1, result, returnSize); // 递归调用，剩余左括号数量减 1
    }
    
    // 如果剩余右括号的数量大于剩余左括号的数量，则可以添加一个右括号
    if (right > left) {
        str[index] = ')'; // 添加右括号
        generateParenthesisHelper(str, left, right - 1, index + 1, result, returnSize); // 递归调用，剩余右括号数量减 1
    }
}

char** generateParenthesis(int n, int* returnSize) {
    // 结果集大小为 Catalan 数 C(2n, n) / (n + 1)
    int size = 1;
    for (int i = 2; i <= n; i++) {
        size *= (4 * i - 2) / (i + 1);
    }
    
    // 创建结果集的数组
    char** result = (char**)malloc(size * sizeof(char*));
    *returnSize = 0;
    
    // 创建一个临时字符串，用于生成有效组合
    char* str = (char*)malloc((2 * n + 1) * sizeof(char));
    str[2 * n] = '\0';
    
    // 递归生成有效组合
    generateParenthesisHelper(str, n, n, 0, result, returnSize);
    
    // 释放临时字符串的内存
    free(str);
    
    return result;
}

int main() {
    int n = 3;
    int returnSize;
    char** result = generateParenthesis(n, &returnSize);
    
    // 打印结果集中的所有有效组合
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", result[i]);
    }
    
    // 释放结果集的内存
    for (int i = 0; i < returnSize; i++) {
        free(result[i]);
    }
    free(result);
    
    return 0;
}

时间复杂度分析： 生成结果集的大小为 Catalan 数 C(2n, n) / (n + 1)。在递归函数中，每次递归调用时，我们有两种选择：添加一个左括号或添加一个右括号。递归的深度为 2n，每个节点有两个分支，因此总共有 2^2n 个节点。而每个节点的操作时间为 O(1)，因此总时间复杂度为 O(2^2n)。对于生成结果集的操作，需要遍历结果集的每个元素，所以时间复杂度为 O(C(2n, n) / (n + 1))。因此，总时间复杂度为 O(2^2n + C(2n, n) / (n + 1))。