关注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, yx 的递归函数。这样我们就不会得到重复的组合。具体地:
    • 我们使用一个哈希映射(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

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