☆打卡算法☆LeetCode 22、括号生成 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个整数n，生成所有有效的括号组合。”

题目链接：

来源：力扣（LeetCode）

链接：22. 括号生成 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

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

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

二、解题

1、思路分析

这道题可以采用暴力破解法，生成所有字符构成的序列，然后检查有效即可。

2、代码实现

采用递归生成所有序列，然后用左括号数量减去右括号数量，判断序列是否有效，代码参考：

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        List<string> res = new List<string>();
        if (n == 0)
            res.Add("");
        else 
        {
            for (var i = 0; i < n; i++)
            {
                foreach (var left in GenerateParenthesis(i))
                {
                    foreach (var right in GenerateParenthesis(n - i - 1))
                    {
                        res.Add("(" + left + ")" + right);
                    }

                }
            }
        }
        return res;   
    }
}

3、时间复杂度

时间复杂度 ： O(2²ⁿn)

对于 2²ⁿn 个序列中的每一个，我们用于建立和验证该序列的复杂度为 O(n)。

空间复杂度： O(n)

除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。

三、总结

回溯的话，要么设置一个全局的唯一状态，然后去递归。

要么自己管理一个栈或队列，每次储存相应的状态，然后去遍历状态树。

我一般不太喜欢函数递归，因为函数调用稍慢些。