回溯算法介绍

具有限界条件的 DFS （Depth first search，深度优先搜索）算法称为回溯算法。

例子

LeetCode 的第 22 题Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:
["((()))","(()())","(())()","()(())","()()()"]
题目目的是给你一个数 n 写出来所有中可能的括号集合。
本题采用的回溯的解题思想：所谓（回溯）Backtracking 都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集。
对于这道题，有以下的限制条件：1、如果左括号已经用完了，则不能再加左括号2、如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。结束条件是：左右括号都已经用完。因此，把上面的思路写一下伪代码：
if (左右括号都已用完) { 加入解集，返回}// 否则开始情况if (还有左括号可以用) { 加一个左括号，继续递归}if (右括号小于左括号) { 加一个右括号，继续递归}
具体实现：
/** * @param {number} n * @return {string[]} */ var generateParenthesis = function (n) { var ans = []; dfs(ans, "", 0, 0, n); return ans;};function dfs(ans, str, left, right, n) { if (left === n && right === n) ans.push(str); if (left < n) { dfs(ans, str "(", left 1, right, n); } if (right < left) { dfs(ans, str ")", left, right 1, n); }}console.log(generateParenthesis(3));// ["((()))", "(()())", "(())()", "()(())", "()()()"]