LeetCode-中等-22-括号生成(C)

图床换了个新的，以前的虽然不错，但是上传后会模糊。这道题还是很费脑子的，我得去加点水。

使用realloc在LeetCode上会增大内存消耗，就很气。

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

已知需要生成出包含n组括号的二维数组，获得所有可能结果后，使用returnSize返回大小，下面简写rSize。

这n组括号中，我们研究左括号的排放位置。

在获得左括号位置时，引入一个存放括号的，大小为n的数组，称为parenthesisPosition，下面简写pPos，

在第i个数组位置，存放第i个左括号的位置，例如下面这个n=4的括号组合中：
((()))()，pPos的内容为0，1，2，6，为了方便研究，我们不以0开头，而以1开头，即nPos的内容为1，2，3，7，
表示这组括号中的第1/2/3/7个位置是左括号。

将所有末尾增长到最大值的情况用 | 标出，
可以看出，第i个左括号的位置不能超过 2 * i -1。

还可以看出，当n=2时，rSize=2，
n=3时，rSize=3+2，
n=4时，rSize=4+3+2+3+2，
那么这有什么用呢？
n=5时，rSize=5+4+3+2+4+3+2+3+2吗？
不，不会，这只会误导我，他唯一的作用就是让我误以为我解出来了。
我没有找到除遍历外更方便的计算方式，因为把第n=5列出来太麻烦了，不好找规律，而如果我解出来了，我除了优化外没有需要新的计算方式的理由了。

上段略过，如果我们将括号的位置当作进制数，第i个括号一旦到 2*i-1，就将第i-1位置进位，
但同时，还需要注意，在十进制中，12579的进位是12580，
而在这里，12579的进位是13456。

看起来不好处理，但实际上，只需要两个循环即可，
但在此之前，我们需要每次循环前，都将第n位的值加1，这样表示下一个括号组合，例如：
上一轮循环后，组合为1 2 4，那么这一次为1 2 5，
如果上一轮为1 2 5，那么这一轮为 1 2 6（此时组合错误，在后面的循环中处理）

在开始下面两个循环前，此时的组合为1 2 5，
末尾自增，变为1 2 6。

第一个循环，从第n位向第2位（因为第1位最大值为1），
比较当前值是否等于 2*i，即 pPos[i-1] = 2*i;（这里的i从1开始，而数组下标从0开始）
如果相等，则将第i-1的值加1，例如：
本次循环是1 2 6，此时循环在第3位，6=2*3，那么第2位值加1，变为1 3 6，之后循环在第2位，3 != 2*2，不处理。

在上一个循环中，我们已将1 2 6改为了1 3 6，在本轮循环中，只需要将错误的值修正即可，
第二轮循环，由第2位向第n位，
一个方便的修正方式，也是方便遍历方式，是：
若第 i 位的位置： pPos[i-1] == 2*i，则将其改为第i-1位+1后的值，那么上次循环产生的1 3 6，就会变成1 3 4。

经过一次末尾自增以及一组翻转的遍历循环后，1 2 5 变成了 1 3 4，符合条件。
试试更复杂的值：1 2 5 7 9，
末尾自增后：1 2 5 7 10
第一轮循环：
1 2 5 8 10
1 2 6 8 10
1 3 6 8 10
第二轮循环
1 3 4 8 10
1 3 4 5 10
1 3 4 5 6
此时，1 2 5 7 9变为了1 3 4 5 6。

这种进位可以正常使用，那么他能正常自增吗？
1 3 4 5 6：
经过末尾自增：1 3 4 5 7
一组翻转的循环条件均不满足，无需修改。
再次末尾自增：1 3 4 5 8
再次末尾自增：1 3 4 5 9
再次末尾自增：1 3 4 5 10
此时第一轮循环中：
1 3 4 6 10
第一轮循环结束，第二轮循环：
1 3 4 6 7
则，1 3 4 5 9转为了1 3 4 6 7，正常增长。

这样，在值增长为1 3 5 7 9时终止循环即可。

适合搭配realloc函数使用，根据增长大小，按需分配空间。

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

char ** generateParenthesis(int n, int* returnSize){
    int i, i2;
    char **parenthesisReturnArray = NULL;
    *returnSize = 0;
    int *parenthesisPosition = (int*)malloc(sizeof(int) * (n+1));   // 括号位置存放数组
    for(i=0;    i<n;    i++){   // 将初始位置数组置为12345...表示左括号存放位置
        parenthesisPosition[i] = i+1;
    }
    parenthesisPosition[n-1] = n-1; // 数组第n位置为n-1，因为后面每次循环都会把它加1，第一次的时候回多出一次。

    for(i=1;    ;  i++){
        for(i2=0;   parenthesisPosition[i2]==(i2+1)*2-1 && i2<n;   i2++);
        if(i2==n) break;    // 如果发现上一组括号存在的位置为13579...则表明已经遍历完全。

        parenthesisPosition[n-1] += 1;
        *returnSize += 1;
        parenthesisReturnArray = (char**)realloc(parenthesisReturnArray, sizeof(char*)*(*returnSize));
        *(parenthesisReturnArray + i-1) = (char*)malloc(sizeof(char) * (2*n+1));

        for(i2=n;   i2>1;   i2--){  
            if(parenthesisPosition[i2-1] == 2*i2){
                parenthesisPosition[i2-2]++;
            }
        }
        for(i2=2;   i2<=n;  i2++){
            if(parenthesisPosition[i2-1] == 2*i2){
                parenthesisPosition[i2-1] = parenthesisPosition[i2-2] + 1;
            }
        }

        int i3; // 根据前两个循环设置各位置括号
        for(i2=1, i3=0;   i2<=2*n;    i2++){
            if(i2 == parenthesisPosition[i3])   {
                parenthesisReturnArray[i-1][i2-1] = '(';
                i3++;
            }
            else parenthesisReturnArray[i-1][i2-1] = ')';
        }
        parenthesisReturnArray[i-1][2*n] = '\0';
    }

    return parenthesisReturnArray;
}