LeetCode刷题 _第22题（Generate Parentheses）_感想

题目描述

菜鸡解法（暴力递归）

看到题目第一眼，感觉和第20题有效的括号很相似，苦思冥想了10分钟没有任何思路（除了暴力递归），试想一下笔试时也没这么多时间考虑，于是想着不管复杂度多少，先AC一下！就这样还磕磕绊绊了半小时，于是诞生了如下垃圾代码


对，你没有看错，120ms，一是想着能不能给递归剪下枝，于是用了两个变量记录当前已存在的左括号数量和右括号数量，当左括号大于一半时返回，不然像((((((这样的太浪费时间，运行了一下，还有24ms，果然暴力递归是不行的！

大神解法

熟悉的那一步到来了，打开Discuss，看了一下大神的解法，真的觉得自己太笨了，除了多用了栈数据结构，效率差在哪里呢？
对于（））这种情况菜鸡解法会继续往下递归，因为前面一对括号在栈中被抵消了，菜鸡的约束条件只是左括号不能大于一半，也就是说还要有当前的右括号数量不能大于左括号数量，于是我在菜鸡解法上加了这个条件，时间还是没优化，看来是频繁的栈操作耗费时间，于是放弃这个解法，改用大神的解法了！