回溯算法解决子集、组合和排列问题 - vcjmhg 的个人博客

之前《"回溯法套路总结与应用" 》这篇文章中，讲了一个回溯算法的通用模板：

1result = []
2def backtrack(路径, 选择列表):
3    if 满足结束条件:
4        result.add(路径)
5        return
6    for 选择 in 选择列表:
7        做选择
8        backtrack(路径, 选择列表)
9        撤销选择

但我们在套用该模板解决实际算法问题时会发现，针对不同类型的问题，会有不同的细节需要注意。因而本篇文章就以子集、组合、排列三类常见搜索问题为例，来讲解使用回溯法来解决这三类问题所需要考虑的不同细节和思路。

问题描述很简单：

在使用回溯法解决问题之前，我们可以根据题意画出搜索过程中产生的回溯树。

我们以示例 1 为例：

首先，空集 [] 肯定是一个子集

然后，以 1 开头的子集：[1],[1,2],[1,3],[1,2,3]。

以 2 开头的子集：[2],[2,3]

以 3 开头的子集：[3]。

然后将上述搜索过程写成一个回溯树：

从回溯树中可以看到，每次在做出一个选择（分支）时，都是添加一个新的未被使用的元素放到搜索列表中。但我们此时会有一个问题，如果来保证搜索时的元素是不重复的呢？

实际上，我们只需要添加一个 start 参数来控制递归，每次通过 for 循环来做出选择的时候，都从 start 来开始遍历。

具体代码如下：

 1class Solution {
 2    List<List<Integer>> res = null;
 3    public List<List<Integer>> subsets(int[] nums) {
 4        res = new LinkedList<>();
 5        LinkedList<Integer> trace = new LinkedList<>();
 6        backtrack(nums, 0, trace);
 7        return res;
 8    }
 9    private void backtrack(int[] nums, int start, LinkedList<Integer> trace) {
10        //结束条件判断
11        res.add(new LinkedList<>(trace));
12	//通过start来控制选择的起始点
13        for(int i = start; i < nums.length; i++) {
14            //做出选择
15            trace.add(nums[i]);
16            //递归回溯
17            backtrack(nums, i + 1, trace);
18            //撤销选择
19            trace.removeLast();
20        }
21    }
22}

组合问题，题目描述如下：

同样的，我们需要根据题意画出对应的回溯树。

以 n = 4, k = 2 为例，

首先，以 1 开头，长度为 2 的组合有：[1,2],[1,3],[1,4]。

以 2 的开头的组合有：[2,3],[2,4]。

以 3 开头的组合有：[3,4]。

画出对应的回溯树：

从回溯树中，我们可以看到组合问题最终搜索到的结果长度是一定的都等于 k，因而回溯结束的条件肯定可以用 k == trace.size() 来进行判断，当相等时，将搜索到的 trace 的结果添加到 res 列表中。另一方面，每一轮的搜索范围也不是所有元素，而是每次搜索添加的元素都是新的未被添加的元素，因而考虑增加一个 start 参数，来控制搜索的起始范围。

具体实现代码如下：

 1class Solution {
 2    List<List<Integer>> res = null;
 3    public List<List<Integer>> combine(int n, int k) {
 4        res = new LinkedList<>();
 5        LinkedList<Integer> trace = new LinkedList<>();
 6        backtrack(n, 1, k, trace);
 7        return res;
 8    }
 9    private void backtrack(int n, int start, int k, LinkedList<Integer> trace) {
10        //当trace中节点数量与k相同时，则记录结果并停止搜索
11        if(k == trace.size()) {
12            res.add(new LinkedList<>(trace));
13            return;
14        }
15        for(int i = start; i <= n; i++) {
16            //做出选择
17            trace.add(i);
18            //回溯
19            backtrack(n,i + 1, k, trace);
20            //撤销选择
21            trace.removeLast();
22        }
23    }
24}

执行结果如下：

组合问题描述如下：

与上述过程类似，根据题意画出其回溯树。

我们以题中例子[1,2,3]为例，

以 1 开头的排列为：[1,2,3],[1,3,2]

以 2 开头的排列为：[2,1,3],[2,3,1]

以 3 开头的排列为：[3,1,2],[3,2,1]

对应的回溯树如下所示：

组合问题和前边排列问题的不同点在于，组合问题选择时，选择的范围会更广，每次做选择的时候，除了 trace 中已经存在的元素之外，其他的元素都要选择一遍。因而在解决该问题时，在"做出选择"之前需要判断当前选择的元素是否在 trace 中已经存在，如果存在则放弃此次选择。具体代码如下：

 1class Solution {
 2    List<List<Integer>> res = null;
 3    public List<List<Integer>> permute(int[] nums) {
 4        res = new LinkedList<>();
 5        LinkedList<Integer> trace = new LinkedList<>();
 6        backtrack(nums, trace);
 7        return res;
 8    }
 9    private void backtrack(int[] nums, LinkedList<Integer> trace) {
10        //搜寻到结果集等于nums.size()则证明当前的一个全排列搜索解决完成
11        if(nums.length == trace.size()) {
12            res.add(new LinkedList<>(trace));
13            return;
14        }
15        for(int num : nums) {
16            //如果选择的元素已经存在
17            if(trace.contains(num)) continue;
18            //做出选择
19            trace.add(num);
20            backtrack(nums,trace);
21            //撤销选择
22            trace.removeLast();
23        }
24    }
25}

运行结果如下：

本文主要讲了通过回溯法如何解决排列、组合、子集这三类问题的基本思路：

组合问题关键点在于用一个 start 来保证每次选择的元素是之前未被选择过的

排列问题关键点在于通过 contains() 来保证每次选择的元素都未被包含在 trace 中

这两类问题回溯结束的时机都是搜索到的元素达到了预定的长度，即我们可以判断 trace 中元素的长度来判断是否终止此次回溯。

而子集问题则不然，因为它的长度是变长的，所以每次进入搜索的第一件事情就是将结果加入到结果集中。

1. 《labuladong 的算法小抄》