当前位置：首页 > article >正文

力扣面试题 08.09. 括号 C语言解法回溯递归动态规划字符串

article 2025/1/11 21:30:52

题目：

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路：

此题首先想到回溯算法。根据我前几篇的联系，已经对回溯有一定了解了。不了解回溯的自行csdn搜索了解。
回溯算法首先明确终止条件：当临时结果字符串的长度等于2n时，表示括号已添加完毕。将这次的结果存入结果数组。
什么时候应该添加（呢？当左括号的数量小于n时，可以添加（
什么时候应该添加）呢？当左括号的数量大于右括号时，可以添加右括号。这样添加的括号总是有效的。
将以上步骤写出回溯函数递归调用，即得解。

C语言代码：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int retSize = 0;
void backtrack(char* temp, char** ret, int n, int len, int lcnt, int rcnt) {
    if(len == 2 * n) {
        temp[len] = '\0';
        ret[retSize] = (char*)malloc((2 * n + 1) * sizeof(char));
        strcpy(ret[retSize], temp);
        retSize++;
        return;
    }
    if(lcnt < n) {
        temp[len] = '(';
        backtrack(temp, ret, n, len + 1, lcnt + 1, rcnt);
    }
    if(lcnt > rcnt) {
        temp[len] = ')';
        backtrack(temp, ret, n, len + 1, lcnt, rcnt + 1);
    }
}

char** generateParenthesis(int n, int* returnSize) {
    retSize = 0;
    char* temp = (char*)malloc((2 * n + 1) * sizeof(char));
    char** ret = (char**)malloc((1 << (2 * n)) * sizeof(char*));
    backtrack(temp, ret, n, 0, 0, 0);
    *returnSize = retSize;
    free(temp);
    return ret;
}

按照回溯模板代码来说，递归之后应该写回溯操作，为什么该题递归操作后面没有回溯操作？

假设我们写了回溯操作，如下：

if (lcnt < n) {
    temp[len] = '(';
    len++;
    backtrack(temp, ret, n, len, lcnt + 1, rcnt);
    len--;  // 回溯
}
if (rcnt < lcnt) {
    temp[len] = ')';
    len++;
    backtrack(temp, ret, n, len, lcnt, rcnt + 1);
    len--;  // 回溯
}

这样的len--是多此一举的。为什么呢？

你之所以在递归后使用 len--，是想恢复 len 的值。但是注意，len 是在递归时通过参数传递的，而不是通过全局变量或指针引用来共享的，因此每次递归调用返回后，len 会自动恢复到调用之前的值，无需手动 len--。

具体来说：