[数据结构与算法]【leetcode】回溯算法专场，排列/组合/子集问题

前言

无论是排列、组合还是子集问题，简单说就是从序列 nums 中用题目给定的规则，得出若干个元素，主要有以下几种变体：

1. 形式一、元素无重复，不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。

   以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。

2. 形式二、元素可重复，不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。

   以组合为例，如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。

3. 形式三、元素无重复，可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。

   以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]。

4. 第四种形式，即元素可重复，可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。

除此之外，题目也可以再添加各种限制条件，比如让你求和为 target 且元素个数为 k 的组合，那这么一来又可以衍生出一堆变体。

但无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可。

子集/组合

子集（元素无重复，不可复选）（78.子集）

好，我们先不考虑如何用代码实现，先回忆一下我们的高中知识，如何手推所有子集？

1. 首先，生成元素个数为 0 的子集，即空集 []，为了方便表示，我称之为 S_0。

2. 然后，在 S_0 的基础上生成元素个数为 1 的所有子集，我称为 S_1：
   

3. 接下来，我们可以在 S_1 的基础上推导出 S_2，即元素个数为 2 的所有子集：
   

   为什么集合 [2] 只需要添加 3，而不添加前面的 1 呢？

   答：因为集合中的元素不用考虑顺序， [1,2,3] 中 2 后面只有 3，如果你向前考虑 1，那么 [2,1] 会和之前已经生成的子集 [1,2] 重复。

   换句话说，我们通过保证元素之间的相对顺序不变来防止出现重复的子集。

4. 接着，我们可以通过 S_2 推出 S_3，实际上 S_3 中只有一个集合 [1,2,3]，它是通过 [1,2] 推出的。

   整个推导过程就是这样一棵树：
   

注意这棵树的特性：

如果把根节点作为第 0 层，将每个节点到根节点之间树枝上的元素作为该节点的值，也就是经过路径

那么第 n 层的所有节点，就是大小为 n 的所有子集。

你比如大小为 2 的子集就是这一层节点的值：

那如果想要计算所有子集，只要遍历这棵多叉树，把所有节点的值收集起来不就行了？直接看代码：

List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> path = new LinkedList<>();

// 主函数
public List<List<Integer>> subsets(int[] nums) {
    backtrack(nums, 0);
    return res;
}

// 回溯算法核心函数，遍历子集问题的回溯树
void backtrack(int[] nums, int start) {

    // 前序位置，每个节点的值都是一个子集
    //「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」
    res.add(new LinkedList<>(track));
    if (start >= nums.length){ //终止条件可不加
        return;
    }
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        path.addLast(nums[i]);
        // 通过 start 参数控制树枝的遍历，避免产生重复的子集
        backtrack(nums, i + 1);
        // 撤销选择
        path.removeLast();
    }
}

组合（元素无重复，不可复选）（77.组合）

比如说，让你在 nums = [1,2,3] 中拿 2 个元素形成所有的组合，你怎么做？

其实你想想就会发现，大小为 2 的所有组合，不就是所有大小为 2 的子集嘛。

所以说组合和子集是一样的：大小为 k 的组合就是大小为 k 的子集。

比如 combine(3, 2) 的返回值应该是：[ [1,2],[1,3],[2,3] ]

这是标准的组合问题，但转换一下就变成子集问题了：

比如：给你输入一个数组 nums = [1,2..,n] 和一个正整数 k，请你生成所有大小为 k 的子集。

还是以 nums = [1,2,3] 为例，刚才是求所有子集，就是把所有节点的值都收集起来；那现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：

还是上面的代码，只需要稍改 base case，控制只收集第 k 层节点的值即可：

List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> path = new LinkedList<>();

// 主函数
public List<List<Integer>> combine(int n, int k) {
    backtrack(n, k, 1);
    return res;
}

void backtrack(int n, int k, int start) {
    // base case
    if (k == path.size()) {
        // 遍历到了第 k 层，收集当前节点的值
        res.add(new LinkedList<>(path));
        return;
    }
    
    // 回溯算法标准框架
    for (int i = start; i <= n; i++) {
        // 选择
        path.addLast(i);
        // 通过 start 参数控制树枝的遍历，避免产生重复的子集
        backtrack(n, k, i + 1);
        // 撤销选择
        path.removeLast();
    }
}

像这样，标准的子集问题也解决了。

子集/组合（元素可重复，不可复选）（90.子集 II）

刚才的标准子集问题输入的 nums 是没有重复元素的，但如果存在重复元素，怎么处理呢？

比如输入 nums = [1,2,2]，你应该输出：[ [],[1],[2],[1,2],[2,2],[1,2,2] ]

为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。

按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：

[ 
    [],
    [1],[2],[2'],
    [1,2],[1,2'],[2,2'],
    [1,2,2']
]

所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：

体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> subsetsWithDup(int[] nums) {
    // 先排序，让相同的元素靠在一起
    Arrays.sort(nums);
    backtrack(nums, 0);
    return res;
}

void backtrack(int[] nums, int start) {
    // 前序位置，每个节点的值都是一个子集
    res.add(new LinkedList<>(path));
    
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        path.addLast(nums[i]);
        backtrack(nums, i + 1);
        path.removeLast();
    }
}

这段代码和之前标准的子集问题的代码几乎相同，就是添加了排序和剪枝的逻辑。

子集/组合（元素无重复，可复选）（39.组合总和）

比如输入 candidates = [1,2,3], target = 3，算法应该返回：[ [1,1,1],[1,2],[3] ]

这道题说是组合问题，但实际上也可以是子集问题：candidates 的哪些子集的和为 target？

我们不妨先思考下，标准的子集/组合问题是如何保证不重复使用元素的？

答案在于 backtrack 递归时输入的参数 start：

// 无重组合的回溯算法框架
void backtrack(int[] nums, int start) {
    for (int i = start; i < nums.length; i++) {
        // ...
        // 递归遍历下一层回溯树，注意参数
        backtrack(nums, i + 1);
        // ...
    }
}

这个 i 从 start 开始，那么下一层回溯树就是从 start + 1 开始，从而保证 nums[start] 这个元素不会被重复使用：

那么反过来，如果我想让每个元素被重复使用，我只要把 i + 1 改成 i 即可：

// 可重组合的回溯算法框架
void backtrack(int[] nums, int start) {
    for (int i = start; i < nums.length; i++) {
        // ...
        // 递归遍历下一层回溯树，注意参数
        backtrack(nums, i);
        // ...
    }
}

这相当于给之前的回溯树添加了一条树枝，在遍历这棵树的过程中，一个元素可以被无限次使用：

当然，如果这样这棵回溯树会永远生长下去，所以我们的递归函数需要设置合适的终止条件，即路径和大于 target 时就没必要再遍历下去了。

这道题的解法代码如下：

List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 path 中的路径和
int pathSum = 0;

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

// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
    // base case，找到目标和，记录结果
    if (pathSum == target) {
        res.add(new LinkedList<>(path));
        return;
    }
    // base case，超过目标和，停止向下遍历
    if (pathSum > target) {
        return;
    }

    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 选择 nums[i]
        pathSum += nums[i];
        path.add(nums[i]);
        // 递归遍历下一层回溯树
        // 同一元素可重复使用，注意参数
        backtrack(nums, i, target);
        // 撤销选择 nums[i]
        pathSum -= nums[i];
        path.removeLast();
    }
}

组合总和 II（40.组合总和 II）

组合问题和子集问题是等价的，所以我们直接看一道组合的题目：

题目的意思，给你输入 candidates 和一个目标和 target，从 candidates 中找出中所有和为 target 的组合。

candidates 可能存在重复元素，且其中的每个数字最多只能使用一次。

其实换个问法就变成子集问题了：请你计算 candidates 中所有和为 target 的子集。

所以这题怎么做呢？对比子集问题的解法，只要额外用一个 pathSum 变量记录回溯路径上的元素和，然后将 base case 改一改即可解决这道题：

List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 path 中的元素之和
int pathSum = 0;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    if (candidates.length == 0) {
        return res;
    }
    // 先排序，让相同的元素靠在一起
    Arrays.sort(candidates);
    backtrack(candidates, 0, target);
    return res;
}

// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
    // base case，达到目标和，找到符合条件的组合
    if (trackSum == target) {
        res.add(new LinkedList<>(path));
        return;
    }
    // base case，超过目标和，直接结束
    if (pathSum > target) {
        return;
    }

    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，值相同的树枝，只遍历第一条
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        path.add(nums[i]);
        pathSum += nums[i];
        // 递归遍历下一层回溯树
        backtrack(nums, i + 1, target);
        // 撤销选择
        path.removeLast();
        pathSum -= nums[i];
    }
}

排序

排列（元素无重复，不可复选）（46.全排序）

比如输入 nums = [1,2,3]，函数的返回值应该是：

[
    [1,2,3],[1,3,2],
    [2,1,3],[2,3,1],
    [3,1,2],[3,2,1]
]

刚才的组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。

但排列问题本身就是让你穷举元素的位置，nums[i] 之后也可以出现 nums[i] 左边的元素，所以之前的有点不一样，需要额外使用 used数组 来标记哪些元素还可以被选择。

标准全排列可以抽象成如下这棵二叉树：

我们用 used数组 标记已经在路径上的元素，避免重复选择，然后收集所有叶子节点上的值，就是所有全排列的结果：

List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> path = new LinkedList<>();
// path 中的元素会被标记为 true
boolean[] used;

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
public List<List<Integer>> permute(int[] nums) {
    used = new boolean[nums.length];
    backtrack(nums);
    return res;
}

// 回溯算法核心函数
void backtrack(int[] nums) {
    // base case，到达叶子节点
    if (path.size() == nums.length) {
        // 收集叶子节点上的值
        res.add(new LinkedList(path));
        return;
    }

    // 回溯算法标准框架
    for (int i = 0; i < nums.length; i++) {
        // 已经存在 path 中的元素，不能重复选择
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        path.addLast(nums[i]);
        // 进入下一层回溯树
        backtrack(nums);
        // 取消选择
        path.removeLast();
        used[i] = false;
    }
}

这样，全排列问题就解决了。

但如果题目不让你算全排列，而是让你算元素个数为 k 的排列，怎么算？

只要改下 backtrack函数 的代码，仅收集第 k 层的节点值即可：

// 回溯算法核心函数
void backtrack(int[] nums, int k) {
    // base case，到达第 k 层，收集节点的值
    if (path.size() == k) {
        // 第 k 层节点的值就是大小为 k 的排列
        res.add(new LinkedList(track));
        return;
    }

    // 回溯算法标准框架
    for (int i = 0; i < nums.length; i++) {
        // ...
        backtrack(nums, k);
        // ...
    }
}

排列（元素可重复，不可复选）（47.全排序 ll）

比如输入 nums = [1,2,2]，函数返回：[ [1,2,2],[2,1,2],[2,2,1] ]，先看解法代码：

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;

public List<List<Integer>> permuteUnique(int[] nums) {
    // 先排序，让相同的元素靠在一起
    Arrays.sort(nums);
    used = new boolean[nums.length];
    backtrack(nums);
    return res;
}

void backtrack(int[] nums) {
    if (path.size() == nums.length) {
        res.add(new LinkedList(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
            continue;
        }
        path.add(nums[i]);
        used[i] = true;
        backtrack(nums);
        path.removeLast();
        used[i] = false;
    }
}

对比一下之前的标准全排列解法代码，这段解法代码只有两处不同：

1. 对 nums 进行了排序。

2. 添加了一句额外的剪枝逻辑。

但是注意排列问题的剪枝逻辑，和子集/组合问题的剪枝逻辑略有不同：新增了 used[i - 1] == false 的逻辑判断。

假设输入为 nums = [1,2,2']，标准的全排列算法会得出如下答案：

[
    [1,2,2'],[1,2',2],
    [2,1,2'],[2,2',1],
    [2',1,2],[2',2,1]
]

显然，这个结果存在重复，比如 [1,2,2'] 和 [1,2',2] 应该只被算作同一个排列，但被算作了两个不同的排列。

所以现在的关键在于，如何设计剪枝逻辑，把这种重复去除掉？

答案是，保证相同元素在排列中的相对位置保持不变。

比如说 nums = [1,2,2'] 这个例子，我保持排列中 2 一直在 2' 前面。

这样的话，你从上面 6 个排列中只能挑出 3 个排列符合这个条件：

[ [1,2,2'],[2,1,2'],[2,2',1] ]

这也就是正确答案。

标准全排列之所以出现重复，是因为把相同元素形成的不同排列序列，视为不同的序列了，但实际上它们应该是相同的；

而如果固定相同元素形成的序列顺序，当然就避免了重复。

那么反映到代码上，你注意看这个剪枝逻辑：

// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}
// 选择 nums[i]

当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

排列（元素无重，可复选）

力扣上没有类似的题目，我们不妨先想一下，nums 数组中的元素无重复且可复选的情况下，会有哪些排列？

比如输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：

[
  [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
  [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
  [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]

标准的全排列算法利用 used数组 进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，那直接去除所有 used数组的剪枝逻辑就行了。

反而更简单了，代码如下：

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();

public List<List<Integer>> permuteRepeat(int[] nums) {
    backtrack(nums);
    return res;
}

// 回溯算法核心函数
void backtrack(int[] nums) {
    // base case，到达叶子节点
    if (path.size() == nums.length) {
        // 收集叶子节点上的值
        res.add(new LinkedList(path));
        return;
    }

    // 回溯算法标准框架
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        path.add(nums[i]);
        // 进入下一层回溯树
        backtrack(nums);
        // 取消选择
        path.removeLast();
    }
}

最后总结

来总结下排列/组合/子集问题的三种形式在代码上的区别。

由于子集问题和组合问题本质上是一样的，无非就是递归终止条件有一些区别，所以把这两个问题放在一起。

1. 形式一、元素无重复，不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。

   /* 组合/子集问题回溯算法框架 */
   void backtrack(int[] nums, int start) {
       // 回溯算法标准框架
       for (int i = start; i < nums.length; i++) {
           // 做选择
           path.addLast(nums[i]);
           // 注意参数 i+1
           backtrack(nums, i + 1);
           // 撤销选择
           path.removeLast();
       }
   }
   
   /* 排列问题回溯算法框架 */
   void backtrack(int[] nums) {
       for (int i = 0; i < nums.length; i++) {
           // 剪枝逻辑
           if (used[i]) {
               continue;
           }
           // 做选择
           used[i] = true;
           path.addLast(nums[i]);
   
           backtrack(nums);
           // 撤销选择
           path.removeLast();
           used[i] = false;
       }
   }
   

2. 形式二、元素可重复，不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。其关键在于排序和剪枝，backtrack 核心代码如下：

   Arrays.sort(nums);
   /* 组合/子集问题回溯算法框架 */
   void backtrack(int[] nums, int start) {
       // 回溯算法标准框架
       for (int i = start; i < nums.length; i++) {
           // 剪枝逻辑，跳过值相同的相邻树枝
           if (i > start && nums[i] == nums[i - 1]) {
               continue;
           }
           // 做选择
           path.addLast(nums[i]);
           // 注意参数
           backtrack(nums, i + 1);
           // 撤销选择
           path.removeLast();
       }
   }
   
   
   Arrays.sort(nums);
   /* 排列问题回溯算法框架 */
   void backtrack(int[] nums) {
       for (int i = 0; i < nums.length; i++) {
           // 剪枝逻辑
           if (used[i]) {
               continue;
           }
           // 剪枝逻辑，固定相同的元素在排列中的相对位置
           if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
               continue;
           }
           // 做选择
           used[i] = true;
           path.addLast(nums[i]);
   
           backtrack(nums);
           // 撤销选择
           path.removeLast();
           used[i] = false;
       }
   }
   

3. 形式三、元素无重复，可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。只要删掉去重逻辑即可，backtrack 核心代码如下：

   /* 组合/子集问题回溯算法框架 */
   void backtrack(int[] nums, int start) {
       // 回溯算法标准框架
       for (int i = start; i < nums.length; i++) {
           // 做选择
           path.addLast(nums[i]);
           // 注意参数
           backtrack(nums, i);
           // 撤销选择
           path.removeLast();
       }
   }
   
   
   /* 排列问题回溯算法框架 */
   void backtrack(int[] nums) {
       for (int i = 0; i < nums.length; i++) {
           // 做选择
           path.addLast(nums[i]);
           backtrack(nums);
           // 撤销选择
           path.removeLast();
       }
   }
   

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生