回溯算法

[wengjq]

概念

具有限界条件的 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)); //  ["((()))", "(()())", "(())()", "()(())", "()()()"]