回溯算法汇总一

[sisterAn]

上周发了篇文章，关于一名 95 后女程序员（4 年前端开发），对现状的担忧与对未来的焦虑担忧，文章一经发出，后台就收到很多反馈，大部分的人都表示认同：

因此，我决定把自己的每日进阶记录下来，有时可能 2-3 天一起，每日内容不多，如果你不清楚怎么做，就和我一起吧，如果你有规划，也可以关注「三分钟学前端」，添加我的微信 pzijun_com，将你的每日进阶记录发送到群群里，我们一起督促学习

回溯算法

什么是回溯算法问题？

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。它就是不断的尝试，直到拿到解。因此它类似于一种暴力穷举的算法，此类问题一般都很少考虑时间复杂度问题

它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解，或得到所有满足要求的解。因此它常采用深度优先遍历（DFS）求解

我们最常遇到的问题，例如：

• 全排列问题
• 括号生成问题
• 组合总和问题
• 树的深度遍历问题

全排列问题

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

它的核心思路就是类似一个多叉树的形式，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

图片来自于：https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png

let permute = function(nums) {
    // 使用一个数组保存所有可能的全排列
    let res = []
    if (nums.length === 0) {
        return res
    }
    let used = {}, path = []
    dfs(nums, nums.length, 0, path, used, res)
    return res
}
let dfs = function(nums, len, depth, path, used, res) {
    // 所有数都填完了
    if (depth === len) {
        res.push([...path])
        return
    }
    for (let i = 0; i < len; i++) {
        if (!used[i]) {
            // 动态维护数组
            path.push(nums[i])
            used[i] = true
            // 继续递归填下一个数
            dfs(nums, len, depth + 1, path, used, res)
            // 撤销操作
            used[i] = false
            path.pop()
        }

    }
}

括号生成问题

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

对应于本题，最开始是 ''，我们可以每次试探增加 ( 或 ) ，注意：

• 加入 ( 的条件是，当前是否还有 ( 可以选择
• 加入 ) 的时候，受到 ( 的限制，如果已选择的结果里的 ( 小于等于已选择里的 ) 时，此时是不能选择 ) 的，例如如果当前是 () ，继续选择 ) 就是 ()) ，是不合法的

代码实现：

const generateParenthesis = (n) => {
    const res = []
    const dfs = (path, left, right) => {
        // 肯定不合法，提前结束
        if (left > n || left < right) return
        // 到达结束条件
        if (left + right === 2 * n) {
            res.push(path)
            return
        }
        // 选择
        dfs(path + '(', left + 1, right)
        dfs(path + ')', left, right + 1)
    }
    dfs('', 0, 0)
    return res
}

组合总和问题

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

• candidates 中的 同一个 数字可以无限制重复被选取 。
• 如果至少一个数字的被选数量不同，则两种组合是不同的。

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

对应于本题，从 candidates 选择数，每个数可以选择多次，使用 index 记录当前选到第几个数，不可向前选择，防止重复，count 为当前满足条件的 index 位的数最多可选 count 次，由 0 ... count 次往后递归

• paths：已选数
• sum：已选数和
• index：当前选到第几个数

var combinationSum = function(candidates, target) {
    let res = [], map = new Map()
    let dfs = function(paths, sum, index) {
        if(sum > target || index > candidates.length) return
        if(target === sum) {
            res.push(paths)
            return 
        }
        // 计算当前数可选的倍数
        let count = Math.floor((target-sum)/candidates[index])
        // 选择当前数
        for(let i = 0; i <= count; i++) {
            dfs(new Array(i).fill(candidates[index]).concat(paths), sum+i*candidates[index], index+1)
        }
    }
    dfs([], 0, 0)
    return res
};

优化：

var combinationSum = function(candidates, target) {
    let res = [], map = new Map()
    let dfs = function(paths, sum, index) {
        if(sum > target || index > candidates.length) return
        if(target === sum) {
            res.push(paths)
            return 
        }
        dfs(paths, sum, index+1)
        if(target-sum>=candidates[index]) {
          dfs([...paths, candidates[index]], sum+candidates[index], index)
        }
    }
    dfs([], 0, 0)
    return res
};