回溯算法实践：括号生成

labuladong原创约 2152 字

本文讲解的例题

LeetCode	力扣	难度
22. Generate Parentheses	22. 括号生成	🟠

前置知识

阅读本文前，你需要先学习：

括号问题可以简单分成两类，一类是前文写过的括号的合法性判断，一类是合法括号的生成。对于括号合法性的判断，主要是借助「栈」这种数据结构，而对于括号的生成，一般都要利用回溯算法进行暴力穷举。

回到正题，看下力扣第 22 题「括号生成」，要求如下：

22. 括号生成 | 力扣 | LeetCode |

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

示例 1：

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

示例 2：

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

提示：

函数签名如下：

java 🟢

List<String> generateParenthesis(int n);

cpp 🤖

vector<string> generateParenthesis(int n);

python 🤖

def generateParenthesis(n: int) -> List[str]:

go 🤖

func generateParenthesis(n int) []string

javascript 🤖

var generateParenthesis = function(n) {};

有关括号问题，你只要记住以下性质，思路就很容易想出来：

回溯思路