回溯算法

1. 简介

‌回溯算法（又名决策树）是一种系统地搜索问题的解的方法，也称为试探法。它的基本思想是从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解。当发现已不满足求解条件时，就“回溯”返回，尝试别的路径‌

2. 例子

例子1：找出给定数组：[2,3,6,7]中和为：target = 7的组合，解：[[2, 2, 3], [7]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void backTrace(int[] nums, List<Integer> path, List<List<Integer>> result) {
    //已走路径path的数组长度等于nums的长度,表示走到叶子节点，所以加到全排列集合
    if (nums.length == path.size()) {
        result.add(new LinkedList(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        //剪枝，排查已经走过的路径
        if (path.contains(nums[i])) {
            continue;
        }
        //做选择，加到当前路径
        path.add(nums[i]);
        //递归，进入下一层的决策
        backTrace(nums, path, result);
        //取消选择
        path.remove(path.size() - 1);
    }
}

例子2：找出给定数组：[1,2,3]中不重复的排列组合，解：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void backTrace(int[] nums, List<Integer> path, List<List<Integer>> result, int target, int start) {
    if (target < 0) {
        return;
    }
    //满足结束条件，加到总路径
    if (target == 0) {
        result.add(new ArrayList(path));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        //可选列表：当前结点大于要走的路径数值
        if (target >= nums[i]) {
            //做选择
            path.add(nums[i]);
            //递归
            backTrace(nums, path, result, target - nums[i], i);
            //撤销选择
            path.remove(path.size() - 1);
        }
    }
}

3. 总结

决策一个回溯问题，实际上就是解决一个决策树的遍历过程。需要考虑这三个问题：

  • 已走路径：已做出选择，走过的路径
  • 可选列表：你当前可以做的选择
  • 结束条件：一般走到决策树的叶子节点，它无法再做别的条件选择
1
2
3
4
5
6
7
8
9
10
11
12
//所有路径集合
List<> allPath  = [];
void backTrace (可选列表，已走路径)：
     if(满足结束条件){
        allPath.add(已走路径);
        return;
     }
     for(选择：可选列表){
        做选择
        backTrace（当前可选列表，已走路径）;
        撤销选择
     }