11.回溯法解决生成括号问题

function backtrack(str, left, right) {}

回溯终止条件：括号总数等于2n。

两个选择（choices）：添加'(' 或添加')'。

添加'('的剪枝条件：left(左括号的数量)小于n。

添加')'的剪枝条件：right(右括号的数量)小于left。（这是一个知识点：在创建括号的过程中，右括号的数量要始终小于左括号，因为一旦右括号的数量大于左括号，这个括号的组合立即无效。)

JS代码：

/** * @param {number} n * @return {string[]} */ var generateParenthesis = function(n) { let res = []; function backtrack(str, left, right) { //回溯终止条件 if (str.length === 2 * n) { res.push(str); return; } //make a choice: add left or add right if (left < n) { backtrack(str + '(', left + 1, right); } //剪枝条件 if (right < left) { backtrack(str + ')', left, right + 1); } } backtrack('', 0, 0); return res; };