大家好，我是前端西瓜哥，今天来看一道回溯题。
求 n 对括号的所有合法组合，要求返回一个字符串数组。比如 n 为 3 时，要求返回：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
代码实现
思路是回溯，题目的特征也比较明显。
我们先看代码实现。
function generateParenthesis(n: number): string[] { const arr: string[] = []; r(arr, '', n, n); return arr; }; // leftRem: 左括号剩余数 // rightRem: 右括号剩余数 function r(arr: string[], str: string, leftRem: number, rightRem: number) { // 左括号使用量超过 n // 以及右括号使用数超过左括号，都是不合法的。 if (leftRem < 0 || rightRem < leftRem) return; if (leftRem === 0 && rightRem === 0) { arr.push(str); return; } r(arr, str + '(', leftRem - 1, rightRem); r(arr, str + ')', leftRem, rightRem - 1); }
这里简单说说回溯是怎么一个原理。
回溯就好比我们遇到岔路时，选择一条路走完后，我们再可以回到当前这个岔路口，走另一条路。岔路走完后，我们又回到上一个岔路，直到所有的路都走完。
可以看出，回溯本质是穷举。
n 对括号问题同样的道理，我们将会遇到 n 个岔路口，每个岔路口，我们有两个选择，是选择左括号呢还是右括号。
r(arr, str + '(', leftRem - 1, rightRem); r(arr, str + ')', leftRem, rightRem - 1);
但我们有可能会得到不合法的组合，有两种情况：
- 左括号使用数量超过 n；
- 在添加括号的过程中，使用的右括号数不能超过左括号数。如果超过了，就说明至少有一个左括号没对象，这不合法。
还有一种情况是右括号数超过 n，但它可以由上面两种情况的组合推导而出，所以就不做讨论了。
下图为 n = 2 时，回溯的过程，其中橙色叉叉代表情况 1，红色叉叉代表情况 2。
当这两种情况发生时，就代表此路不通，不需要继续递归下去了，直接 return。
if (leftRem < 0 || rightRem < leftRem) return;
此外我们还需要知道 str 字符串变成一个合法的组合的时机。
可以是 leftRem 和 rightRem 都为 0，可以是 str 长度为 n。但我们偷懒没传 n，所以就用前者吧。
if (leftRem === 0 && rightRem === 0) { arr.push(str); return; }
结尾
求 n 对括号的所有合法组合的题目，解法为回溯。每次选择左括号或右括号进入下一个阶段，并更新对应的一些状态（剩余数减一）。
这些状态会在后续的回溯中作为判断合法与否的条件，在特定时机结束递归。
我是前端西瓜哥，欢迎关注我。
