关注Java领域相关技术 记录有趣的事情

LeetCode-40. 组合总和 II

US-B.Ralph
US-B.Ralph
2020-09-11

问题地址

LeetCode每日一题/2020-09-10

LeetCode40. 组合总和 II

问题描述

规则

  • 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
  • candidates 中的每个数字在每个组合中只能使用一次。

说明

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例

  • 示例一：
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
  • 示例二：
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

解析

解题思路

数据操作分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

官方解法

方法一：递归

思路：

  • 由于我们需要求出所有和为 \textit{target} 的组合，并且每个数只能使用一次，因此我们可以使用递归 + 回溯的方法来解决这个问题：
    • 我们用 \text{dfs}(\textit{pos}, \textit{rest}) 表示递归的函数，其中 \textit{pos} 表示我们当前递归到了数组 \textit{candidates} 中的第 \textit{pos} 个数，而 \textit{rest} 表示我们还需要选择和为 \textit{rest} 的数放入列表作为一个组合；
    • 对于当前的第 \textit{pos} 个数，我们有两种方法：选或者不选。如果我们选了这个数，那么我们调用 \text{dfs}(\textit{pos}+1, \textit{rest} – \textit{candidates}[\textit{pos}]) 进行递归，注意这里必须满足 \textit{rest} \geq \textit{candidates}[\textit{pos}]。如果我们不选这个数，那么我们调用 \text{dfs}(\textit{pos}+1, \textit{rest}) 进行递归；
    • 在某次递归开始前，如果 \textit{rest} 的值为 0，说明我们找到了一个和为 \textit{target} 的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。
  • 上述算法就是一个标准的递归 + 回溯算法，但是它并不适用于本题。这是因为题目描述中规定了解集不能包含重复的组合，而上述的算法中并没有去除重复的组合。
    • 例如当 \textit{candidates} = [2, 2]，\textit{target} = 2 时，上述算法会将列表 [2][2] 放入答案两次。
  • 因此，我们需要改进上述算法，在求出组合的过程中就进行去重的操作。我们可以考虑将相同的数放在一起进行处理，也就是说，如果数 \textit{x} 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择 0, 1, \cdots, y 次 x 的递归函数。这样我们就不会得到重复的组合。具体地：
    • 我们使用一个哈希映射（HashMap）统计数组 \textit{candidates} 中每个数出现的次数。在统计完成之后，我们将结果放入一个列表 \textit{freq} 中，方便后续的递归使用。
    • 列表 \textit{freq} 的长度即为数组 \textit{candidates} 中不同数的个数。其中的每一项对应着哈希映射中的一个键值对，即某个数以及它出现的次数。
    • 在递归时，对于当前的第 \textit{pos} 个数，它的值为 \textit{freq}[\textit{pos}][0]，出现的次数为 \textit{freq}[\textit{pos}][1]，那么我们可以调用

dfs(pos+1,rest−i×freq[pos][0])

  • 即我们选择了这个数 i 次。这里 i 不能大于这个数出现的次数，并且 i \times \textit{freq}[\textit{pos}][0] 也不能大于 \textit{rest}。同时，我们需要将 i 个 \textit{freq}[\textit{pos}][0] 放入列表中。

  • 这样一来，我们就可以不重复地枚举所有的组合了。

  • 我们还可以进行什么优化（剪枝）呢？一种比较常用的优化方法是，我们将 \textit{freq} 根据数从小到大排序，这样我们在递归时会先选择小的数，再选择大的数。这样做的好处是，当我们递归到 \text{dfs}(\textit{pos}, \textit{rest}) 时，如果 \textit{freq}[\textit{pos}][0] 已经大于 \textit{rest}，那么后面还没有递归到的数也都大于 \textit{rest}，这就说明不可能再选择若干个和为 \textit{rest} 的数放入列表了。此时，我们就可以直接回溯。

复杂度分析

  1. 时间复杂度 O(2^n \times n)，其中 n 是数组 \textit{candidates} 的长度。在大部分递归 + 回溯的题目中，我们无法给出一个严格的渐进紧界，故这里只分析一个较为宽松的渐进上界。在最坏的情况下，数组中的每个数都不相同，那么列表 \textit{freq} 的长度同样为 n。在递归时，每个位置可以选或不选，如果数组中所有数的和不超过 \textit{target}，那么 2^n 种组合都会被枚举到；在 \textit{target} 小于数组中所有数的和时，我们并不能解析地算出满足题目要求的组合的数量，但我们知道每得到一个满足要求的组合，需要 O(n) 的时间将其放入答案中，因此我们将 O(2^n) 与 O(n) 相乘，即可估算出一个宽松的时间复杂度上界。

    • 由于 O(2^n \times n) 在渐进意义下大于排序的时间复杂度 O(n \log n)，因此后者可以忽略不计。
  2. 空间复杂度O(n)。除了存储答案的数组外，我们需要 O(n) 的空间存储列表 \textit{freq}、递归中存储当前选择的数的列表、以及递归需要的栈。

编码实现

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

精彩评论

跳转地址1：回溯算法 + 剪枝（Java、Python）

一句话解题

  • 一句话题解：按顺序搜索，设置合理的变量，在搜索的过程中判断是否会出现重复集结果。重点理解对输入数组排序的作用和 参考代码 中大剪枝和小剪枝 的意思。

与第 39 题（组合之和）的差别

  • 这道题与上一问的区别在于：
    • 第 39 题：candidates 中的数字可以无限制重复被选取；
    • 第 40 题：candidates 中的每个数字在每个组合中只能使用一次。
  • 相同点是：相同数字列表的不同排列视为一个结果。

思路–如何去掉重复的集合（重点）

  • 为了使得解集不包含重复的组合。有以下 2 种方案：

    • 使用 哈希表 天然的去重功能，但是编码相对复杂；
    • 这里我们使用和第 39 题和第 15 题（三数之和）类似的思路：不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果 。注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。

  • 由第 39 题我们知道，数组 candidates 有序，也是 深度优先遍历 过程中实现「剪枝」的前提。

  • 将数组先排序的思路来自于这个问题：去掉一个数组中重复的元素。很容易想到的方案是：先对数组 升序 排序，重复的元素一定不是排好序以后相同的连续数组区域的第 11 个元素。也就是说，剪枝发生在：同一层数值相同的结点第 22、33 … 个结点，因为数值相同的第 11 个结点已经搜索出了包含了这个数值的全部结果，同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 11 个结点更多，并且是第 11 个结点的子集。（说明：这段文字很拗口，大家可以结合具体例子，在纸上写写画画进行理解。）

说明

  • 解决这个问题可能需要解决 第 15 题（三数之和）、 第 47 题（全排列 II）、 第 39 题（组合之和）的经验；
  • 对于如何去重还不太清楚的朋友，可以参考当前题解的 高赞置顶评论 。

编码实现

参考代码Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Solution {

    public List<List<Integer>> combinationSum2(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<>(len);
        dfs(candidates, len, 0, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param len        冗余变量
     * @param begin      从候选数组的 begin 位置开始搜索
     * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
     * @param path       从根结点到叶子结点的路径
     * @param res
     */
    private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
            if (target - candidates[i] < 0) {
                break;
            }

            // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.addLast(candidates[i]);
            // 调试语句 ①
            // System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

            // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
            dfs(candidates, len, i + 1, target - candidates[i], path, res);

            path.removeLast();
            // 调试语句 ②
            // System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
        }
    }

    public static void main(String[] args) {
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        Solution solution = new Solution();
        List<List<Integer>> res = solution.combinationSum2(candidates, target);
        System.out.println("输出 => " + res);
    }
}

参考代码Python

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(begin, path, residue):
            if residue == 0:
                res.append(path[:])
                return

            for index in range(begin, size):
                if candidates[index] > residue:
                    break

                if index > begin and candidates[index - 1] == candidates[index]:
                    continue

                path.append(candidates[index])
                dfs(index + 1, path, residue - candidates[index])
                path.pop()

        size = len(candidates)
        if size == 0:
            return []

        candidates.sort()
        res = []
        dfs(0, [], target)
        return res

参考代码C++

// author:rmokerone
#include <iostream>
#include <vector>

using namespace std;

class Solution {

private:
    vector<int> candidates;
    vector<vector<int>> res;
    vector<int> path;
public:
    void DFS(int start, int target) {
        if (target == 0) {
            res.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) {
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            path.push_back(candidates[i]);
            // 元素不可重复利用，使用下一个即i+1
            DFS(i + 1, target - candidates[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        DFS(0, target);
        return res;
    }
};

跳转地址2：漫谈回溯 | 长文 | 手画图解 | 40. 组合总和 II

前言

  • 今天是9.10教师节，感谢所有在传道受业解惑的人。Teaching is a work of heart.

思路

  • 以 [2,5,2,1,2], target = 5 为例。
  • 每个节点都作出选择，选一个数，看看下一个选择受到哪些限制：选过的不能再选，且不能产生相同的组合。去做剪枝（如下图所标）。
  • 当和为 target，找到一个正确的解，加入解集。且当和 >= target，已经爆掉了，不用继续选了，结束当前递归，继续搜别的分支，找齐所有的解。
  • 因此，回到上一个节点，撤销当前选择的数字，去进入下一个分支。

与39题对比

  • 第 39 题：元素可以重复使用，组合不能重复。
  • 本题：元素不可以重复使用，组合不能重复。
const combinationSum = (candidates, target) => {
  const res = [];
  const dfs = (start, temp, sum) => {
    if (sum >= target) {        // 爆掉了，不用继续选数了
      if (sum == target) {      // 加入解集
        res.push(temp.slice()); // temp的拷贝
      }
      return;                   // 结束当前递归
    }
    for (let i = start; i < candidates.length; i++) { // 枚举出选择，从start开始
      temp.push(candidates[i]);          // 加入“部分解”
      dfs(i, temp, sum + candidates[i]); // 往下继续选择，同时sum累加上当前数字
      temp.pop();                        // 撤销选择
    }
  };
  dfs(0, [], 0);
  return res;
};
  • 本题只需改动三点：
    1. 给定的数组可能有重复的元素，先排序，使得重复的数字相邻，方便去重。
    2. for 循环枚举出选项时，加入下面判断，忽略掉同一层重复的选项，避免产生重复的组合。比如[1,2,2,2,5]中，选了第一个 2，变成 [1,2]，第一个 2 的下一选项也是 2，跳过它，因为选它，就还是 [1,2]。
if (candidates[i - 1] == candidates[i] && i - 1 >= start) {
    continue;
}

3. 当前选择的数字不能和下一个选择的数字重复，递归传入i+1，避免与当前选的i重复，这样每次选，就不会选过往选过的同一个数。

dfs(i + 1, temp, sum + candidates[i]);

编码实现

const combinationSum2 = (candidates, target) => {
  candidates.sort();    // 排序
  const res = [];

  const dfs = (start, temp, sum) => { // start是索引 当前选择范围的第一个
    if (sum >= target) {        // 爆掉了，不用继续选了
      if (sum == target) {      // 满足条件，加入解集
        res.push(temp.slice()); // temp是地址引用，后续还要用，所以拷贝一份
      }
      return;                   // 结束当前递归
    }
    for (let i = start; i < candidates.length; i++) {             // 枚举出选择
      if (candidates[i - 1] == candidates[i] && i - 1 >= start) { // 当前选项和隔壁选项一样，跳过
        continue;
      }
      temp.push(candidates[i]);              // 作出选择
      dfs(i + 1, temp, sum + candidates[i]); // 递归，向下选择，并更新sum
      temp.pop();                            // 撤销选择，
    }
  };

  dfs(0, [], 0);
  return res;
};

再谈我理解的回溯

回溯的要素

  • 我们关心，当前局面下，我们有什么选择，作了一个选择之后，下一个选择会有什么限制。
  • 解空间树的节点是动态的，当前的选择决定了下一个选择是怎么展开的。
  • 所以，不仅要关注 options，还要关注 restraints 约束。
  • 前者用于展开出一棵解的空间树，后者用于为这棵树剪枝，剪去不能产生正确解的节点，避免无效搜索。
  • 第三个要素：目标（结束条件），明确了目标，就知道何时去将解加入解集。
  • 并且让你知道：探索到某一步时，发现当前的部分解不能通向正确的完整解，搜下去没有意义。
  • 此时回退一步，撤销当前的选择，回到上一个选择的状态，做别的选择。
  • 此路不通，退回去，尝试别的路，是一个「choose, explore, unchoose」的过程。

套路做法

  • 用 for 循环去枚举出所有的选择
  • 做出一个选择
  • 基于这个选择，继续往下选择（递归）
  • 上面的递归结束了，撤销这个选择，进入 for 循环的下一次迭代

回溯 与 嵌套循环

  • 回溯是一种算法，递归不是算法，是一种计算机解决问题的方式。
  • 回溯是借助递归实现的。如果回溯不借助递归，它只能借助循环。
  • 用 for 循环枚举出当前的选项，选了一个，选下一个，又要嵌套一层循环，枚举出可选的选项。
  • 如果要选很多个，就导致多重的循环嵌套，很费力也很丑。
  • 于是借助递归解决，因为递归和子递归就是层级嵌套的关系。
  • 而且，树在结构上，具有高度的重复性，每一个节点，都是当前子树的根节点，调用递归函数负责当前子树的搜索。

虚拟的解空间树

  • 回溯算法并没有显式地创建数据结构，也不是基于已有的数据结构做搜索。
  • 它是隐式地，通过递归，构建出一棵解的空间树。这个空间树中包含了所有的解。
  • 然后通过 dfs 的搜索方式，把解给全部找出来。
  • 如果说它难，应该难在确定出容易搜索（经过充分的剪枝）的解空间结构，剩下的 dfs 和回溯就比较简单了。
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

1 + 20 =