数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
提示:
1 <= n <= 8
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
用left和right表示有几个左括号和几个右括号。
限制:
1、必须从左括号开始, 并且已右括号结束。
2、不允许右括号的个数比左括号多
3、当 left == n, right == n 的时候说明该存储了。
对于retArr的大小是试出来的。。。定的小不够用。N的4次方正好满足了最大 n == 8的场景。
/** * Note: The returned array must be malloced, assume caller calls free(). */ void GetLeft(char **retArr, char *str, int n, int *returnSize, int left, int right) { if (left == n + 1) { return; } str[left + right - 1] = '('; GetLeft(retArr, str, n, returnSize, left + 1, right); GetRight(retArr, str, n, returnSize, left, right + 1); } void GetRight(char **retArr, char *str, int n, int *returnSize, int left, int right) { if (right > left) { return; } str[left + right - 1] = ')'; if (left + right == n * 2) { str[left + right] = '\0'; retArr[*returnSize] = (char *)malloc(sizeof(char) * (n * 2 + 1)); strcpy(retArr[*returnSize], str); *returnSize += 1; return; } GetLeft(retArr, str, n, returnSize, left + 1, right); GetRight(retArr, str, n, returnSize, left, right + 1); } char ** generateParenthesis(int n, int* returnSize){ char **retArr = (char **)malloc(sizeof(char *) * pow(n, 4)); *returnSize = 0; char *str = (char *)malloc(sizeof(char) * n * 2 + 1); GetLeft(retArr, str, n, returnSize, 1, 0); return retArr; }