当前位置：首页 > article >正文

算法-回溯

article 2024/9/25 20:53:06

何谓回溯

正如标题所言，今天我们来讲解回溯算法，回溯的定义网上一大把，而且还不容易懂，这里来谈谈我对回溯的理解。首先我们先来对齐一个认知，任何基础算法都很简单，只需要认真训练就是可以掌握的，不要因为他的名字觉得很高深就认为它很难。为什么这么说呢？这是因为一切的基础算法都源于对现实世界的常见问题的计算机解法。而我们就生活在现实生活中，所以这些问题的解决思想我们早就知道，我们唯一不知道的是这种解决思想如何在计算机的世界中实现仅此而已。所以我们无需把算法认为有多么的高深。如果你认同这个认知，那么就继续往下看

既然所有的算法都只不过是对现实世界常见问题的计算机解法，那么回溯解决的是现实世界中哪类问题呢？在我看来，回溯解决的是不重复，不遗漏的枚举所有可能的结果这类问题，这类问题在数学中被称为排列组合，我们甚至可以认为回溯就是排列组合在计算机中的一个实现。在数学中排列组合尚且有公式，有技巧。那么回溯也不例外。

回溯的核心：构造出多阶段决策模型，对应的数据结构就是决策树，其实就是一颗多叉树而已。只要你能根据问题构造出多阶段决策模型，那么代码就是信手拈来，不过话虽如此，但是如果遵循一定的代码模版，可以更好的进入在题目中理解回溯，最后更容易掌握回溯，毕竟知识从实战中来嘛。这里给出回溯的代码模版

public void backTrack(选择列表,当前进行的阶段，总的阶段,path) {
  if (阶段完成) {
    if (path是我们需要的解) {
         加入到最终的集合里
    }
    return
  }
  
  //遍历所有选择列表，并进入下一个阶段
  for (一个选择 : 选择列表) {
    path.add(选择);
    backTrack(下一个阶段的选择列表，当前阶段 + 1,总阶段,path);
    path.remove(这个选择)
  }
}

既然如此，话不多说，我们来看两道算法题，练习一下回溯。

例题子集

https://leetcode.cn/problems/subsets-ii/description/

题目描述

给你一个整数数组 `nums` ，其中可能包含重复元素，请你返回该数组所有可能的

子集（幂集）。解集 **不能** 包含重复的子集。返回的解集中，子集可以按 **任意顺序** 排列。

**示例 1：**

```Java
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
```

**示例 2：**

```Java
输入：nums = [0]
输出：[[],[0]]
```

根据题意，我们可以总结出这个问题的一个特点：要求返回所有可能的解。很明显这是回溯要解决的哪类问题的特点。于是这道题就可以使用回溯解决。回溯的核心：构造出一棵多阶段决策树，构造这样一棵树，我认为可以分为两步，首先明确得到一个解需要几个阶段。然后需要在每个阶段中，遍历这个阶段的选择列表，并根据题目要求判断某个选择是否可以进入下一个阶段。让我们看看这道题该如何明确这两点

第一个点：那么需要分几个阶段？换句话说得到一个解需要几步，题目要求的解是一个子集，那么得到一个子集需要几步呢？我认为是集合个数的步数，比如例子中[1,2,2]，我认为可以分为3步。第一步，1这个数是不是该子集的元素，第二步2这个数是不是该子集的元素，第三步第二个2是不是该子集的元素。

第二个点：我们需要明确每个阶段的选择列表，根据第一点划分的步骤，那么每一步的选择列表就是当前这个数是子集的元素，以及当前这个数不是子集的元素。而且由于题目要求不能出现重复的子集，我们需要通过举例子，发现重复子集的规律，并对选择列表进行一定的限制。针对这道题，通过举例子我们发现的规律是这样的，在这个数字不是该子集的元素的选择时，进入下一阶段时，我们构造的下一阶段的选择列表中就不能包含这个数。（这里需要你举例发现规律，我替代不了你）

到此回溯解法的核心两个点就明确了，那么代码就如下面这样：

public class LC08_Subsets_With_Dup {
    private List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<Integer> path = new ArrayList<>(n);
        subsetsWithDup_r(nums,0,n,path);
        return resList;
    }

    private void subsetsWithDup_r(int[] nums, int k, int n, List<Integer> path) {
        // 阶段完成
        if (k == n) {
            resList.add(new ArrayList<>(path));
            return;
        }

        // 第一种选择：当前数是该子集的元素
        path.add(nums[k]);
        subsetsWithDup_r(nums,k+1,n,path);
        path.remove(path.size() - 1);

        // 第二种选择：当前数不是该子集的元素
        while (k + 1 < n && nums[k + 1] == nums[k] ) {
            k++;
        }
        subsetsWithDup_r(nums,k + 1,n,path);
        
    }
}

这段代码针对“构造的下一阶段的选择列表中就不能包含这个数”这个要求取了一个巧，先排序，再移除连续相等的数。这样做的好处即节省了空间也节约了创建一个下一阶段选择列表的时间

俗话说的好，念念不忘，必有回响，刷题也是如此多多练习，多多思考一定能够学会。下面给出常见的回溯题