题目描述
标签：中等 字符串 回溯 递归
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
plaintext
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
思路
方法一：动态规划（个人感觉比较好理解）
n的括号组合可以由n-1的括号组合得到，所以可以使用动态规划的思想，从n=1开始，逐步计算n=2，n=3…的括号组合。
javascript
var generateParenthesis = function (n) {
let pre = ['()']
let res = new Set() //使用set去重
for (let i = 2; i <= n; i++) { //因为n=1时已经有了结果，所以从2开始
for (let j = 0; j < pre.length; j++) {
for (let k = 0; k < pre[j].length; k++) {
const tmp = pre[j].split('')
tmp.splice(k, 0, '()')
res.add(tmp.join(''))
}
}
pre = Array.from(res)
res.clear()
}
return pre
}
方法二：深度优先搜索（DFS）
看图说话（大佬的图好强）：题解图片出处
javascript
var generateParenthesis = function (n) {
const res = []
function dfs(str, l, r) {
if (l > r) {
// 左括号小于右括号数量 剪枝 注意边界条件
return
}
if (r === 0 && l === 0) {
res.push(str)
return
}
l > 0 && dfs(str + '(', l - 1, r)
r > 0 && dfs(str + ')', l, r - 1)
}
dfs('', n, n)
return res
}