22. 括号生成

难度：中等

题目

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

Reference

题解

回溯算法

• 当左括号数量小于括号对数时，可以添加左括号
• 当右括号数量小于左括号数量时，可以添加右括号

按照如上方法生成的括号组合可以保证一定是有效的。

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

void dfs(char *currentStr, int n, int left, int right, char **ret, int *returnSize)
{
    if (left == n && right == n)
    {
        ret[*returnSize] = (char *)malloc(sizeof(char) * (2 * n + 1));
        strcpy(ret[*returnSize], currentStr);
        *returnSize += 1;
        return;
    }
    if (left < n)
    {
        currentStr[left + right] = '(';
        dfs(currentStr, n, left + 1, right, ret, returnSize);
    }
    if (right < left)
    {
        currentStr[left + right] = ')';
        dfs(currentStr, n, left, right + 1, ret, returnSize);
    }
}
char ** generateParenthesis(int n, int* returnSize){
    const int maxLen = 10000;
    *returnSize = 0;
    char **ret = (char **)malloc(sizeof(char *) * maxLen),
         *buffer = (char *)memset(malloc(sizeof(char) * (2 * n + 1)), 0, sizeof(char) * (2 * n + 1));
    dfs(buffer, n, 0, 0, ret, returnSize);
    return ret;
}

评论