637，回溯算法解子集 II

Original 博哥数据结构和算法 2022-05-10

问题描述

来源：LeetCode第90题

难度：中等

给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

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

示例 1：

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

示例 2：

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

提示：

1<=nums.length<=10
-10<=nums[i]<=10

回溯算法解决

前面我们讲过593，经典回溯算法题-全排列和594，回溯算法解含有重复数字的全排列 II，他们的区别一个是求全排列一个是求子集。其实原理都差不多，都是使用的回溯算法。做这题之前我们首先要搞懂什么是子集，就是从原数组任意删除m(0<=m<=length)个元素，剩下的元素构成的数组就是原数组的子集。

全排列是每次都需要从数组中选择一个没有选择过的元素，而子集不同，他必须是从当前元素后面选择，比如数组[1,2,3]的全排列有[2,3]，但不会有[3,2]。搞懂了这点，那么这题就简单了。很久以前讲过类似的451，回溯和位运算解子集，只不过第451题没有重复的元素。而这题有重复的，所以我们需要过滤掉重复的子集。我们就以数组[1,2,2,3]举例来画个图看一下，为了区分两个元素2我使用了不同的颜色。

这里出现了重复的子集，那么怎么过滤掉重复的呢，就是在同一深度的两个不同的分支，如果当前元素和前面的元素相同，我们就跳过。如下图所示。

其实原理很简单，具体也可以看下594，回溯算法解含有重复数字的全排列 II的剪枝，两者之间有异曲同工之妙。最后我们再来看下代码。

public List<List<Integer>> subsetsWithDup(int[] nums) {
    //先对数组进行排序，这样相同的元素就会在一起，便于过滤
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, res, new ArrayList<>(), 0);
    return res;
}

/**
 * @param nums     原始数组
 * @param res      需要返回的结果
 * @param tempList 当前路径上的元素
 * @param level    遍历到第几层
 */
private void backtrack(int[] nums, List<List<Integer>> res, List<Integer> tempList, int level) {
    //每条路径上所选择的元素组成的数组都是子集，所以都要添加到集合res中
    res.add(new LinkedList<>(tempList));
    //这里遍历的时候每次都有从之前选择元素的下一个开始，所以这里i的初始值是level
    for (int i = level; i < nums.length; i++) {
        //剪枝，过滤掉重复的
        if (i != level && nums[i] == nums[i - 1])
            continue;
        //选择当前元素
        tempList.add(nums[i]);
        //递归到下一层
        backtrack(nums, res, tempList, i + 1);
        //撤销选择
        tempList.remove(tempList.size() - 1);
    }
}