題解

給定 n 對括號，要求編寫一個函數(shù)生成所有合法的括號組合。合法的括號組合必須滿足每一對括號中的左括號必須先于右括號，并且括號數(shù)量必須平衡。

題目描述

輸入：

• 一個整數(shù) n，表示括號的對數(shù)，滿足 $0\le n\le 10$。

輸出：

• 返回一個包含所有合法括號組合的字符串數(shù)組。

示例1

輸入：

1

輸出：

["()"]

示例2

輸入：

2

輸出：

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

題解思路

這個問題是一個典型的遞歸回溯問題。我們可以通過遞歸來生成所有可能的括號組合。具體步驟如下：

1. 用遞歸函數(shù)生成括號的組合。
2. 每次遞歸調(diào)用時，有兩個選擇：
   • 如果左括號還沒有用完，就添加一個左括號 '('。
   • 如果右括號的數(shù)量小于左括號的數(shù)量，且右括號還沒有用完，就添加一個右括號 ')'。
3. 當左右括號的數(shù)量都達到了 n 時，表示一個合法的組合已經(jīng)完成，將其加入結(jié)果數(shù)組。

時間復雜度和空間復雜度

• 時間復雜度：O($2^n$)，因為每一層遞歸有兩種選擇（添加左括號或右括號）。
• 空間復雜度：O($n$)，由于遞歸調(diào)用棧的深度是 n，每次遞歸都在 2n 長度的字符串上操作。

代碼實現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 深度優(yōu)先搜索（DFS）函數(shù)，用于生成所有有效的括號組合* * @param left 左括號的數(shù)量* @param right 右括號的數(shù)量* @param ret 存儲所有生成的括號組合的數(shù)組* @param path 當前路徑，即當前生成的括號組合* @param n 括號對數(shù)* @param returnSize 當前已生成的括號組合數(shù)量*/
void DFS(int left, int right, char **ret, char* path, int n, int *returnSize) {// 如果左括號和右括號的數(shù)量都等于 n，說明生成了一個有效的括號組合if (left == n && right == n) {// 為當前括號組合分配內(nèi)存，長度為 2n + 1（包括字符串終止符）ret[*returnSize] = malloc(sizeof(char) * (2 * n + 1));if (ret[*returnSize] == NULL) {printf("Memory allocation failed\n");exit(1);}// 將當前路徑復制到結(jié)果數(shù)組中for (int i = 0; i < 2 * n; i++) {ret[*returnSize][i] = path[i];}ret[*returnSize][2 * n] = '\0'; // 添加字符串終止符// 增加已生成的括號組合數(shù)量(*returnSize)++;return;}// 如果左括號的數(shù)量小于 n，可以添加一個左括號if (left < n) {path[left + right] = '('; // 在當前路徑中添加左括號DFS(left + 1, right, ret, path, n, returnSize); // 遞歸調(diào)用，繼續(xù)生成}// 如果右括號的數(shù)量小于左括號的數(shù)量且小于 n，可以添加一個右括號if (right < left && right < n) {path[left + right] = ')'; // 在當前路徑中添加右括號DFS(left, right + 1, ret, path, n, returnSize); // 遞歸調(diào)用，繼續(xù)生成}
}/*** 主函數(shù)，生成所有有效的括號組合* * @param n 括號對數(shù)* @param returnSize 返回的括號組合數(shù)量* @return 存儲所有有效括號組合的數(shù)組*/
char** generateParenthesis(int n, int *returnSize) {// 預(yù)分配足夠大的空間存儲結(jié)果，這里假設(shè)最多有 2000 種組合char** ret = (char**)malloc(sizeof(char*) * 2000);if (ret == NULL) {printf("Memory allocation failed\n");exit(1);}*returnSize = 0; // 初始化返回的括號組合數(shù)量為 0// 為當前路徑分配內(nèi)存，長度為 2n + 1（包括字符串終止符）char* path = (char*)malloc(sizeof(char) * (2 * n + 1));if (path == NULL) {printf("Memory allocation failed\n");exit(1);}// 調(diào)用 DFS 函數(shù)生成所有有效的括號組合DFS(0, 0, ret, path, n, returnSize);// 釋放當前路徑的內(nèi)存free(path);return ret;
}

解析

1. DFS函數(shù)的遞歸邏輯：

   • DFS(left, right, ret, str, n, returnSize)是遞歸的核心函數(shù)，left 和 right 分別表示已使用的左括號和右括號數(shù)量。
   • 如果left和right都達到了n，就將當前字符串str（存放括號組合）存入ret數(shù)組。
   • 如果left < n，我們可以繼續(xù)添加左括號。
   • 如果right < left，我們可以繼續(xù)添加右括號。

2. 空間分配：

   • 結(jié)果數(shù)組ret被分配了2000個空間，可以容納所有合法組合（理論上可能達到O(4^n)個組合，但實際上不會達到這么多）。
   • 每個合法的括號組合是一個長度為2n的字符串，因此str的長度是2n。

3. 返回值：

   • ret返回存放合法括號組合的數(shù)組，returnSize返回合法組合的數(shù)量。

總結(jié)

通過遞歸的方式，我們能夠高效地生成所有合法的括號組合。遞歸回溯方法簡潔而直觀，適合解決此類組合生成的問題。