Young Kbt blog
Young Kbt
2022-06-18
目录

算法思想 - 回溯算法

# 概念

回溯法和分枝限界法都是基于搜索的算法，是对枚举法的改进，避免无效的搜索。回溯法实际上是一个类似穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯（即回退），尝试别的路径。回溯法有 通用解题法 之称。它适合于解一些组合数较大的最优化问题。

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

  • 找到一个可能存在的正确的答案
  • 在尝试了所有可能的分步方法后宣告该问题没有答案

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将回溯到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。

「回溯算法」与「深度优先遍历」都有「不撞南墙不回头」的意思。「回溯算法」强调了「深度优先遍历」思想的用途，用一个不断变化的变量，在尝试各种可能的过程中，搜索需要的结果。强调了回退操作对于搜索的合理性。而「深度优先遍历」强调一种遍历的思想。

# 搜索与遍历

我们每天使用的搜索引擎帮助我们在庞大的互联网上搜索信息。搜索引擎的「搜索」和「回溯搜索」算法里「搜索」的意思是一样的。

搜索问题的解，可以通过遍历实现。所以很多教程把「回溯算法」称为爆搜（暴力解法）。因此回溯算法用于搜索一个问题的所有的解，通过深度优先遍历的思想实现。

# 剪枝

我们都知道搜索算法一般是基于两种方法来进行的（深度优先 DFS 和广度优先 BFS），而这两算法都是基于二叉搜索树的进行的。学过数据结构和算法的都知道二叉搜索树存在很多的分支，很难一次性拿到想要的结果，尤其是当输入参数较大时，二叉搜索树的分支大规模增加的时候，此时，由于搜索过程需要走很多条完全于与结果不相关的路线，所以剪枝思想就出现了。

剪枝一种可以提高搜索算法时间和空间效率的技巧，经过剪枝和其他优化策略优化过的算法在执行效率上远超一般未经剪枝的算法。甚至有些暴力搜索过不了时限的算法，也可以通过各种剪枝 + 优化大大缩短算法运行时间，成功通过时效限制。由此可见剪枝对于搜索算法的重要性。因此，剪枝对于学习算法和在工作中与算法打交道的人来说都是一类不得不学的知识点。

剪枝字面理解就是判断某些条件是否满足，如果不满足，则后面的条件也不再满足，不需要再往后搜索，而回溯是基于搜索的算法，所以可以在搜索的过程，进行剪枝，排除掉不在往后遍历的条件。

# 模板

基础的回溯法有一定的模板，具体问题具体添加代码。

元素允许重复

class Solution {
    public List<List<Integer>> solution(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        if (n == 0) {
            return ans;
        }
        List<Integer> list = new ArrayList<Integer>();
        dfs(nums, n, list, 0, ans);
        return ans;
    }

    public void dfs(int[] nums, int n, List<Integer> list, int depth, List<List<Integer>> ans) {
        if (depth == n) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = depth; i < n; i++) { // 可能也有 for (int i = 0; i < n; i++)
            // 添加元素
            list.add(nums[i]);
            // 继续递归
            dfs(nums, n, list, depth + 1, ans);
            // 撤销操作，回溯
            list.remove(list.size() - 1);
        }
    }
}
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
26
27

元素不允许重复，则利用 used 数组来确定当前元素已经被使用。

public class Solution {
    public List<List<Integer>> solution(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        if (n == 0) {
            return ans;
        }
		// 创建 used 数组
        boolean[] used = new boolean[n];
        List<Integer> list = new ArrayList<Integer>();

        dfs(nums, n, 0, list, used, ans);
        return ans;
    }

    private void dfs(int[] nums, int n, int depth, List<Integer> list, boolean[] used, List<List<Integer>> ans) {
        if (depth == n) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                list.add(nums[i]);
                used[i] = true;
                dfs(nums, n, depth + 1, list, used, ans);
                // 回溯
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}
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
26
27
28
29
30
31
32
33

# 例题

# 例 1

39. 组合总和 (opens new window)

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

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

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选，7 = 7 。 仅有这两种组合。

示例 2

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

输入: candidates = [2], target = 1 输出: []

# 分析

深度优先遍历数组时，用 path 存放遍历的值，并将遍历的值减去 target，如果等于 0，则代表 path 的元素满足条件，保存起来，然后返回上一个状态，即回溯，再用其他值减去 target 进行判断。

如果遍历的值减去 target 小于 0，则代表超出条件，进行回溯，返回上一个状态，然后重新找其他的值与 target 相减。

依次遍历。

# 代码

简单代码：

public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }
}
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
26
27
28
29
30
31
32
33
34
35
36

剪枝代码：

public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            // 重点理解这里剪枝，前提是候选数组已经有序，
            if (target - candidates[i] < 0) {
                break;
            }
            
            path.addLast(candidates[i]);
            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
        }
    }
}
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
26
27
28
29
30
31
32
33
34
35

另一种方式，从后面往前面遍历

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(candidates, ans, target, 0, new ArrayList<>());
        return ans;
    }
    
    public void dfs(int[] candidates, List<List<Integer>> ans, int target, int deep, List<Integer> list) {
        if(deep == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }
        // 先遍历到后面，从后面开始往前面判断
        dfs(candidates, ans, target, deep + 1, list);
        if (target - candidates[deep] >= 0) {
            list.add(candidates[deep]);
            dfs(candidates, ans, target - candidates[deep], deep, list);
            list.remove(list.size() - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 例 2

46. 全排列 (opens new window)

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1] 输出：[[1]]

# 分析

从 [1, 2, 3] 到 [1, 3, 2] ，深度优先遍历是这样做的，从 [1, 2, 3] 回到 [1, 2] 的时候，需要撤销刚刚已经选择的数 3，因为在这一层只有一个数 3 我们已经尝试过了，因此程序回到上一层，需要撤销对 2 的选择，好让后面的程序知道，选择 3 了以后还能够选择 2。

# 代码

代码一

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        Deque<Integer> path = new ArrayDeque<>(len);

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     Deque<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.addLast(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, res);

                used[i] = false;
                path.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

上面代码创建很多中间变量，这些中间变量很多时候是我们不需要的，会有一定空间和时间上的消耗。所以进行优化：

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        // 首先是特判
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            // 3、不用拷贝，因为每一层传递下来的 path 变量都是新建的
            res.add(path);
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                // 1、每一次尝试都创建新的变量表示当前的"状态"
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(nums[i]);

                boolean[] newUsed = new boolean[len];
                System.arraycopy(used, 0, newUsed, 0, len);
                newUsed[i] = true;

                dfs(nums, len, depth + 1, newPath, newUsed, res);
                // 2、无需回溯
            }
        }
    }
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

上面都是再遍历的时候进行判断值，这里可以先将元素存起来，然后在遍历的时候，交换元素位置，接着再后面的无论满不满足条件，都进行回溯，返回上一个状态。如果满足，则将结果存起来，不满足，直接 return。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<Integer>();
        for (int num : nums) {
            list.add(num);
        }
        dfs(nums.length, list, 0, ans);
        return ans;
    }

    public void dfs(int n, List<Integer> list, int start, List<List<Integer>> ans) {
        if (start == n) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < n; i++) {
            // 动态维护数组
            Collections.swap(list, start, i);
            // 继续递归填下一个数
            dfs(n, list, start + 1, ans);
            // 撤销操作，回溯
            Collections.swap(list, start, i);
        }
    }
}
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
26

参考：https://leetcode.cn/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

编辑此页 (opens new window)
#算法
更新时间: 2023/09/18, 16:34:13
算法思想 - 贪心算法
算法模板 - 滑动窗口模板

← 算法模板 - 滑动窗口模板→

最近更新
01
技术随笔 - Element Plus 修改包名 原创
11-02
02
Reactor - 扩展性
11-02
03
Reactor - 最佳实践
11-02
更多文章>
Theme by Vdoing | Copyright © 2021-2024 Young Kbt | blog
桂ICP备2021009994号