算法（五）回溯算法

算法（五）回溯算法

1. 简介

  • 回溯算法是算法设计中的一种方法
  • 回溯算法是一种渐进式寻找并构建问题解决方式的策略
  • 回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯并选择另一个动作，直到将问题解决

回溯算法解决适用条件：

  • 有很多路
  • 这些路中，有的是死路
  • 通常需要递归来模拟所有的路

2. LeetCode题

46. 全排列

解题思路：

  • 要求：
    • 所有排列情况
    • 没有重复元素
  • 有出路、有死路
  • 考虑使用回溯算法

解题步骤：

  • 用递归模拟出所有情况
  • 遇到包含重复元素的情况，就回溯
  • 收集所有达到递归终点的情况，并返回

78. 子集

解题思路：

  • 要求：
    • 所有子集
    • 没有重复元素
  • 有出路、有死路
  • 考虑使用回溯算法

解题步骤：

  • 用递归模拟出所有情况
  • 保证接的数字都是后面的数字
  • 收集所有到达递归终点的情况，并返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var var subsets = function (nums) {
    const res = [];
    const backtrack = (path, length, start) => {
        if (path.length === length) {
            res.push(path);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            backtrack(path.concat(nums[i]), length, i + 1);
        }
    }
    for (let i = 0; i <= nums.length; i++) {
        backtrack([], i, 0);
    }
    return res;
};
  • 时间复杂度：$O(n*2^N)$
  • 空间复杂度：$O(N)$

其他：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var subsets = function (nums) {
    let res = []
    let path = []
    const backtracking = (start) => {
        // 可以不需要加终止条件，因为start >= nums.length，本层for循环本来也结束了
        res.push(path.slice())
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i])
            backtracking(i + 1)
            path.pop() //回溯
        }
    }
    backtracking(0)
    return res
};