C语言算法-解答括号生成问题的C语言实现

题目

给定一个数字 n，生成所有可能的有效括号组合。

引言

括号生成问题可以使用回溯法来解决，通过枚举所有可能的括号组合，并使用剪枝操作来减少无效的组合。解决这个问题需要使用递归和回溯的方法。

算法思路

我们将使用回溯法来解决括号生成问题。

算法的步骤如下：

1. 创建一个结果集 result，用于存储所有有效的括号组合。

2. 使用递归函数 backtrack，该函数接受以下参数：

   • current：当前生成的括号组合字符串。
   • open：已经放置的左括号的个数。
   • close：已经放置的右括号的个数。
   • n：需要生成的括号对数。

3. 在递归函数中，首先判断递归终止条件：

   • 如果 open 和 close 的数量都达到了 n，说明已经生成了一个有效的括号组合，将其添加到结果集中。

4. 对于每个位置，有两种选择：

   • 放置一个左括号，如果 open 的数量小于 n。
   • 放置一个右括号，如果 close 的数量小于 open 的数量。

5. 递归调用 backtrack，更新参数：

   • 如果放置了左括号，则 open 的数量加一。
   • 如果放置了右括号，则 close 的数量加一。
   • 更新 current，将放置的括号字符添加到 current 中。

6. 在递归函数返回之前，需要回溯操作：

   • 如果放置了左括号，则 open 的数量减一。
   • 如果放置了右括号，则 close 的数量减一。
   • 更新 current，将放置的括号字符从 current 中移除。
7. 返回结果集 result。

代码实现

下面是使用C语言实现的代码：

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

void backtrack(char** result, char* current, int open, int close, int n, int* count, int index) {
    if (index == 2 * n) {
        current[index] = '\0';
        result[*count] = (char*)malloc(sizeof(char) * (2 * n + 1));
        strcpy(result[*count], current);
        (*count)++;
        return;
    }

    if (open < n) {
        current[index] = '(';
        backtrack(result, current, open + 1, close, n, count, index + 1);
    }

    if (close < open) {
        current[index] = ')';
        backtrack(result, current, open, close + 1, n, count, index + 1);
    }
}

char** generateParenthesis(int n, int* returnSize) {
    char** result = (char**)malloc(sizeof(char*) * (2 * n * (2 * n - 1) / 2));
    char* current = (char*)malloc(sizeof(char) * (2 * n + 1));
    int count = 0;
    backtrack(result, current, 0, 0, n, &count, 0);
    *returnSize = count;
    return result;
}

int main() {
    int n = 3;
    int returnSize;
    char** result = generateParenthesis(n, &returnSize);

    printf("Result:\n");
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", result[i]);
        free(result[i]);
    }

    free(result);

    return 0;
}

算法分析

该算法的时间复杂度为 O(4^n / √n)，其中 n 是括号对数。对于每个位置，有两种选择：放置左括号或放置右括号。在递归的过程中，每个位置都有两种选择，总共有 2^(2n) 种可能的组合，但由于在生成过程中进行了剪枝操作，所以最终的组合数量为 4^n / √n。

空间复杂度为 O(4^n / √n)，算法使用了额外的存储空间来存储结果集。

示例和测试

示例输入1:

n = 3

示例输出1:

Result:
((()))
(()())
(())()
()(())
()()()

示例输入2:

n = 1

示例输出2:

Result:
()

总结

本文使用C语言实现了解答括号生成问题的代码。通过使用回溯法，我们能够生成所有可能的有效括号组合。该算法的时间复杂度为 O(4^n / √n)，空间复杂度为 O(4^n / √n)。