leetcode22：括号生成

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    回溯法，深度优先搜索

    每次可以放置左括号的条件：剩余左括号的数目大于 0。
    每次可以放置右括号的条件：剩余右括号的数目大于 0，并且大于左括号的数目。

    时间复杂度：O(4^n/sqrt(n))
        对于每个括号组合，都有两个选择：添加左括号或添加右括号。
        在最坏的情况下，可能需要生成所有 2^n 个括号组合，然后从中筛选出有效的组合。
        实际上有效的组合远小于这个数，约等于卡特兰数，其增长速度为 O(4^n/sqrt(n))。
    空间复杂度：O(n)  
        除了答案数组之外，所需要的空间取决于递归栈的深度，
        每一层递归函数需要 O(1) 的空间，最多递归 2n 层。
*/
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;    // 记录所有合法的括号组合
        string path;           // 回溯过程中的路径
        dfs(res, path, n, n);  // 可用的左括号和右括号数量初始化为 n
        
        return res;
    }

    void dfs(vector<string>& res, string path, int lc, int rc) {
        if (lc == 0 && rc == 0) res.push_back(path);
        if (lc > 0) dfs(res, path + '(', lc - 1, rc);
        if (rc > 0 && lc < rc) dfs(res, path + ')', lc, rc - 1);
    }
};

/*
    思路同上

    题目可以改写为：
        2n 个位置，每个位置可以放置 '(' 或 ')'，组成的所有括号组合中，有多少个是合法的？
    这是典型的回溯算法，暴力穷举即可。
    为了减少不必要的穷举，合法的括号组合性质如下：
        1.左括号的数量不超过 n
        2.右括号的数量不超过左括号
	从左往右算的话，最后左右括号数量相等，说明这个括号组合是合法的。
*/
class Solution_1 {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;    // 记录所有合法的括号组合
        string path;           // 回溯过程中的路径
        dfs(res, path, n, n);  // 可用的左括号和右括号数量初始化为 n
        
        return res;
    }

    void dfs(vector<string>& res, string& path, int left, int right) {
        // 不符合的情况：左括号剩下的多
        if (left > right) return;
        // 不符合的情况：数量小于 0
        if (left < 0 || right < 0) return;
        // 符合的情况：所有括号都恰好用完
        if (left == 0 && right == 0) {
            res.push_back(path);
            return;
        }

        // 尝试放一个左括号
        path.push_back('('); // 选择
        dfs(res, path, left - 1, right);
        path.pop_back();     // 撤消选择

        // 尝试放一个右括号
        path.push_back(')'); // 选择
        dfs(res, path, left, right - 1);
        path.pop_back();     // 撤消选择
    }
};

int main() {
    Solution solution;
    int n = 3;
    vector<string> combinations = solution.generateParenthesis(n);
    cout << "All combinations of " << n << " pairs of parentheses are:" << endl;
    for (const string& combination : combinations) {
        cout << combination << ",";
    }
    cout << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   回溯算法：
       使用回溯算法生成所有可能的括号组合。
       回溯算法通过递归模拟所有可能的选择路径，每次选择一个括号加入当前组合，并在递归返回时恢复状态。
   选择条件：
       左括号的数量不能超过 n。
       右括号的数量不能超过左括号的数量。
   结束条件：
       如果当前字符串的长度达到 2n，说明找到了一个有效的组合，将其加入结果列表。

   时间复杂度：O(n*4^n/sqrt(n))
       生成所有有效括号组合的时间复杂度为 O(4^n/sqrt(n))，这是卡特兰数的渐进公式。
       每个组合的生成时间复杂度为 O(n)，因为需要将组合加入结果列表。
       因此，总时间复杂度为 O(n*4^n/sqrt(n))。
   空间复杂度：O(n*4^n/sqrt(n))
       递归调用栈的深度为 O(n)。
       当前组合 current 的空间复杂度为 O(n)。
       结果列表 result 的空间复杂度为 O(4^n/sqrt(n))，因为需要存储所有组合。
       因此，总空间复杂度为 O(n*4^n/sqrt(n))。
*/
func generateParenthesis(n int) []string {
    var result []string

    var dfs func(path string, left, right int)
    dfs = func(path string, left, right int) {
        // 如果当前字符串长度为 2n，则说明是一个有效的组合
        if len(path) == n*2 {
            result = append(result, path)
            return
        }
        // 如果左括号数量小于 n，则可以添加一个左括号
        if left < n {
            dfs(path+"(", left+1, right)
        }
        // 如果右括号数量小于左括号数量，则可以添加一个右括号
        if right < left {
            dfs(path+")", left, right+1)
        }
    }

    // 开始回溯
    dfs("", 0, 0)
    return result
}

func main() {
	// 测试用例
	testCases := []struct {
		n        int
		expected []string
	}{
		{
			n: 3,
			expected: []string{
				"((()))", "(()())", "(())()", "()(())", "()()()",
			},
		},
		{
			n: 1,
			expected: []string{
				"()",
			},
		},
	}

	for i, tc := range testCases {
		fmt.Printf("Test Case %d, Input: n = %d\n", i+1, tc.n)
		result := generateParenthesis(tc.n)

		if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}