【力扣刷题】22. 括号生成

一、题目描述

来源:力扣（LeetCode）

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

示例 1：

示例 2：

提示：

• 1 <= n <= 8

二、思路分析

使用回溯法，分成3种情况:

1. 当左右括号剩余数量一样多时，必定只能选择(，且后续不可能能选)，因为())是不合法的只能是()(，所以直接break，另外据此推论，在回溯过程中左括号数量一定小于等于右括号数量。
2. 当左括号剩余数量大于0时且左右括号数量不等时，先选择左括号再选择右括号回溯（先右后左也可以）
3. 当只有右括号时候，就直接选择，之后由于也没有其他选择直接break

三、代码实现

四、运行结果

image.png

总结

考虑种类问题时，首先使用回溯算法，要明确怎么枝剪