回溯算法总结

我们将回溯想象成在深度遍历一颗数，每一种路径都是一个选择，在 backtrack 函数开头判断结果是否添加此选项。
在回溯中，我们想象一个数组 [] 为路径，那么每次选择都是往路径中添加节点，因此，就要考虑每次节点的选项。
在下题中，for(let i = idx; i < nums.length; i++)，这里idx可以视为路径中此刻的位置，类似于二叉树的当前层数。
因为不可以包含重复的子集，所以之前走过的节点不可以再取了，因此我们在进入回溯的时候idx需要+1

剑指 Offer II 079. 所有子集
给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

var subsets = function(nums) {
    const res = []
    const backtrack = (idx, path) => {
        res.push([...path])

        for(let i = idx; i < nums.length; i++){
            path.push(nums[i]);   // 添加
            backtrack(i + 1, path)
            path.pop();   //回溯
        }
    }
    backtrack(0, [])
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

回溯算法在选择当前节点的时候，遍历当前所有的可选项。
本题可作为回溯题目的模板，主要变化在于递归终止条件、每轮可遍历的选项和选择结果路径。

剑指 Offer II 081. 允许重复选择元素的组合
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

var combinationSum = function(candidates, target) {
    const res = []
    const backtrack = (idx, sum, path) => {
        if(sum === target){   // 添加结果路径 
            res.push([...path]) 
        }else if(sum > target) return //如果sum超过target就直接return

        for(let i = idx; i < candidates.length; i++){
            path.push(candidates[i])
            backtrack(i, sum + candidates[i], path)  //下次还可以选此元素
            path.pop()
        }
    }

    backtrack(0, 0, [])
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解答：本题需要注意的是元素可以多次选择，那么在进入下次选择的时候，依旧可以选择当前元素，idx不需要+1。

剑指 Offer II 082. 含有重复元素集合的组合
给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

var combinationSum2 = function(candidates, target) {
    const res = []
    candidates.sort()
    
    const backtrack = (idx, sum, path) => {
        // 终止条件
        if(sum === target){  
            res.push([...path])  //添加合法路径
            return
        }else if(sum > target) return

        for(let i = idx; i < candidates.length; i++){  
            if(i > idx && candidates[i] === candidates[i - 1]) continue  // 跳过重复的数字
            path.push(candidates[i])
            backtrack(i + 1, sum + candidates[i], path)   // 不能重复使用，所以 i + 1
            path.pop()
        }
    }
    
    backtrack(0, 0, [])
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

本题与之前题目不同之处在于数组中含有重复数字，因此如果按照之前的遍历方法而不加以限制，那么就会出现不同路径但是结果相同的解集。在遇见重复数字的时候，我们的想法是只选择第一次，而忽略后续相同的数字。那么就需要先对数组排序，让相同的元素靠在一起，如果nums[i] === nums[i - 1]，就跳过。
如何只选择第一次呢？我们想象一下遍历的时候，当前所有可选项都是孩子节点，并且这些孩子节点已经排好序了，对于重复的节点，只选第一个，也就是nums[i] === nums[i - 1]，就跳过。
每次第一个可选项是必取的，所以还要添加 i > idx 判断。当前节点和前一节点出现重复是可接受的，因为我们的限制是在当前节点层。

剑指 Offer II 083. 没有重复元素集合的全排列
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

var permute = function(nums) {
    const res = []

    const backtrack = (path) => {
        if(path.length === nums.length){
            res.push([...path])
            return;
        }

        for(let i = 0; i < nums.length; i++){
            if(path.indexOf(nums[i]) === -1){
                path.push(nums[i])
                backtrack(path)
                path.pop()
            }
        }
    }
    backtrack([])
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

无重复全排列问题我比较倾向于通过记录当前数字是否被使用，然后遍历所有数字，逐步往路径中加入未使用的数字。

剑指 Offer II 084. 含有重复元素集合的全排列
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

var permuteUnique = function(nums) {
    const res = []
    const used = new Array(nums.length).fill(false)
    nums.sort()

    const backtrack = (path) => {
        if(path.length === nums.length){
            res.push([...path])
            return;
        }

        for(let i = 0; i < nums.length; i++){
            if(used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])){ //重复值，只选择第一条路径
                continue
            }
            path.push(nums[i])
            used[i] = true
            backtrack(path)
            path.pop()
            used[i] = false
        }
    }
    backtrack([])
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

类似于无重复全排列，在有重复全排列中，我们在遍历的时候依旧要遍历当前所有未访问过的可选项，所以used[i]===true说明该选项已被访问过，跳过。
对于重复值我们只取第一个，这里借用了一个访问数组来判断是否访问过第一个重复值，i > 0 && nums[i] === nums[i - 1] && !used[i - 1]，如果第一个重复值已访问过，那么used[i-1]===true，跳过当前i选项。

剑指 Offer II 085. 生成匹配的括号
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

var generateParenthesis = function(n) {
    const res = []

    const backtrack = (left, right, path) => {
        if(left > right || left < 0 || right < 0) return  //剩余左括号大于右括号或者一种括号<0，退出
        else if(left === 0 && right === 0){
            res.push(path.join(''))
            return
        }

        // 遍历两种选择
        backtrack(left - 1, right, [...path, '(']) //当前位置添加左括号
        backtrack(left, right - 1, [...path, ')']) //当前位置添加右括号
    }

    backtrack(n, n, [])
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

看到找有效组合、有效路径这种题目就要想到回溯，看到求最大、最小、路径总数就要想到dp。
本体一样套用模板，因为每次可选项是左括号和右括号，那么变量就是左右括号的剩余数量，终止条件为任一括号数量小于0或者是剩余左括号数量大于右括号，这样一定是不合法的组合。遍历的时候只需要遍历两种选择就够了。
剑指 Offer II 087. 复原 IP
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

var restoreIpAddresses = function(s) {
    const res = []
    if(s.length > 12) return []  // 防止超时

    const backtrack = (idx, dot, path) => {
        if(dot === 0 && idx === s.length && check(path)){ // 点都添加了&&字符都添加了&&ip合法
            res.push(path.join(''))
            return
        }else if(idx === s.length) return // 已添加完所有字符，但不是合法ip
        else if(dot < 0) return // 3个点都用完了
        else if(idx - path.lastIndexOf('.') > 4){ // 当前位置距离上一个点超过4，前一段地址肯定超过255
            return 
        }

        backtrack(idx + 1, dot - 1, [...path, s[idx], '.'])
        backtrack(idx + 1, dot, [...path, s[idx]])
    }

    backtrack(0, 3, [])
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

仍然是套用模板，但是本题对于终止条件需要好好考虑，每个位置都可以加点或者不加点，在终止条件处判断当前路径是否合法，以及是否需要提前终止。

剑指 Offer II 102. 加减的目标值
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

var findTargetSumWays = function(nums, target) {
    let res = 0;

    const backtrack = (idx, pre) => {
        if(idx === nums.length && pre === target){
            res++
            return
        }else if(idx === nums.length && pre !== target) return

        // 两种选择
        backtrack(idx + 1, pre + nums[idx])
        backtrack(idx + 1, pre - nums[idx])
    }

    backtrack(0, 0)
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

回溯很简单，因为题目限制了nums的长度不超过20，所以不会超时。
本题也是经典dp题，neg为取负值，那么剩余正值就是 sum - neg，保证(sum - neg) - neg = target，那么可以转化为 neg = (sum - target) / 2，在数组中求和为 neg 的组合数。

var findTargetSumWays = function(nums, target) {
    let sum = nums.reduce((prev, cur) => prev + cur, 0)
    let n = nums.length, diff = sum - target
    if(diff < 0 || diff % 2 !== 0) return 0
    let neg = diff / 2
    // dp[i][j]表示在前i个数中去到和为j的组合数
    const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0))
    dp[0][0] = 1
    for(let i = 1; i <= n; i++){
        const num = nums[i - 1] // 当前值
        for(let j = 0; j <= neg; j++){
            dp[i][j] = dp[i - 1][j] // dp[i][j]至少为dp[i-1][j]
            if(num <= j){ //当前数可取
                dp[i][j] += dp[i - 1][j - num]
            }
        }
    }
    return dp[n][neg]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剑指 Offer II 110. 所有路径
给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出（不要求按顺序）。
graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ），若为空，就是没有下一个节点了。

var allPathsSourceTarget = function(graph) {
    const res = []
    const n = graph.length
    const backtrack = (cur, path) => {
        if(cur === n - 1){
            res.push([...path, cur])
        }else if(path.indexOf(cur) > -1){ //此节点走过了
            return
        }
        path.push(cur)
        for(let next of graph[cur]){ // 遍历当前节点可到达的节点
            backtrack(next, path)
        }
        path.pop()
    }

    backtrack(0, [])
    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我这里做法考虑了有环图的情况，可以避免经过重复节点，因此需要把添加操作拉到循环外面。