C语言实现括号有效组合生成 - 递归算法详解

使用 C 语言生成 n 对括号的有效组合

问题分析： 本问题要求打印出 n 对括号的所有有效组合，即左右括号必须正确匹配。例如当 n=3 时，有效组合为'((()))', '(()())', '(())()', '()(())', '()()()'。

解题思路： 可以使用递归的方法解决本问题。首先定义一个递归函数，该函数有三个参数：当前要生成的字符串、左括号的数量、右括号的数量。递归函数的终止条件是当左右括号的数量都为 n 时，将当前字符串打印出来。在递归函数中，首先判断是否可以放置左括号，即左括号的数量是否小于 n，如果满足条件，则将左括号的数量加 1，并且将当前字符串加上一个左括号，然后递归调用自己。接着判断是否可以放置右括号，即右括号的数量是否小于左括号的数量，如果满足条件，则将右括号的数量加 1，并且将当前字符串加上一个右括号，然后递归调用自己。最后，在递归函数的外部调用该函数，传入初始参数空字符串、0 和 0。

完整的代码注释：

#include <stdio.h>

// 递归函数，用于生成括号的有效组合
void generateParenthesis(char* str, int left, int right) {
    // 当左右括号的数量都为 n 时，打印当前字符串
    if (left == right && left == n) {
        printf('%s\n', str);
        return;
    }
    // 如果左括号的数量小于 n，可以放置左括号
    if (left < n) {
        str[left+right] = '('; // 在当前字符串的末尾加上一个左括号
        generateParenthesis(str, left+1, right); // 递归调用自己，在左括号的数量加 1 的基础上继续生成
    }
    // 如果右括号的数量小于左括号的数量，可以放置右括号
    if (right < left) {
        str[left+right] = ')'; // 在当前字符串的末尾加上一个右括号
        generateParenthesis(str, left, right+1); // 递归调用自己，在右括号的数量加 1 的基础上继续生成
    }
}

int main() {
    int n = 3; // 括号对数
    char str[2*n + 1]; // 生成的括号字符串，长度为 2n+1，最后一个字符为 '\0'
    generateParenthesis(str, 0, 0); // 调用递归函数，初始时左右括号的数量都为 0
    return 0;
}

时间复杂度分析： 递归函数的时间复杂度为 O(2^n)，因为在每一层递归的时候，都会有两个分支，即放置左括号和放置右括号。总共有 2^n 个叶子结点，所以时间复杂度为 O(2^n)。