数字n代表生成括号的对数,请你用c语言动态规划的思想写一段代码,用于能够生成所有可能的并且有效的括号组合,代码尽可能简洁
时间: 2024-02-19 17:57:45 浏览: 84
下面是一段使用动态规划思想的 C 语言代码,用于生成所有可能的并且有效的括号组合:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char **generateParenthesis(int n, int *returnSize) {
if (n == 0) {
*returnSize = 0;
return NULL;
}
char **result = (char **)malloc(sizeof(char *) * 10000);
int count = 0;
int left = 0, right = 0;
char *temp = (char *)malloc(sizeof(char) * (2 * n + 1));
memset(temp, 0, sizeof(char) * (2 * n + 1));
generate(result, &count, temp, n, left, right);
*returnSize = count;
return result;
}
void generate(char **result, int *count, char *temp, int n, int left, int right) {
if (left == n && right == n) {
char *s = (char *)malloc(sizeof(char) * (2 * n + 1));
strcpy(s, temp);
result[*count] = s;
(*count)++;
return;
}
if (left < n) {
temp[left + right] = '(';
generate(result, count, temp, n, left + 1, right);
temp[left + right] = '\0';
}
if (right < left) {
temp[left + right] = ')';
generate(result, count, temp, n, left, right + 1);
temp[left + right] = '\0';
}
}
```
该代码使用了递归方式,其中 generate() 函数用于生成所有有效的括号组合,result 数组用于存储所有有效的括号组合,count 变量用于记录有效括号组合的数量,temp 数组用于存储当前生成的括号序列,n 表示生成括号的对数,left 和 right 分别表示已经添加的左括号和右括号的数量。
阅读全文