当前位置:首页 > 精彩博文 > javaScript 的数据结构与算法(八)——回溯算法
javaScript 的数据结构与算法(八)——回溯算法
时间:2020-02-28 作者: 分类:javascript

概念

具有限界条件的 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)); //  ["((()))", "(()())", "(())()", "()(())", "()()()"]
微信公众号: i81for
扫一扫关注 · 佳节领红包
公益性全栈资源网站,鸣谢默默付出的博主、工程师、架构师们。
网站内容来源技术大牛的辛勤结晶。
81For 技术网站 Copyright ©2019 备案号:津ICP备19001147号-2