子集 II
难度:
标签:
题目描述
给你一个整数数组 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
代码结果
运行时间: 32 ms, 内存: 15.2 MB
// Java Stream solution
// 思路：
// 1. 使用Java Stream生成幂集。
// 2. 使用集合来去重。
// 3. 对结果集进行排序以确保顺序。
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class StreamSolution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // 排序
Set<List<Integer>> resultSet = IntStream.range(0, 1 << nums.length)
.mapToObj(i -> IntStream.range(0, nums.length)
.filter(j -> (i & (1 << j)) != 0)
.mapToObj(j -> nums[j])
.collect(Collectors.toList()))
.collect(Collectors.toSet());
return resultSet.stream().sorted((a, b) -> a.size() - b.size()).collect(Collectors.toList());
}
}解释
方法:
这个题解使用了回溯算法来生成所有可能的子集。首先将数组进行排序，以方便去除重复的子集。然后定义一个回溯函数，通过维护一个路径数组 path，依次将数组中的元素加入路径中，并递归调用回溯函数，直到达到终止条件。在递归过程中，通过判断当前元素是否与前一个元素相同，来避免生成重复的子集。最后返回所有生成的子集。
时间复杂度:
O(n * 2^n)
空间复杂度:
O(n * 2^n)
代码细节讲解
🦆
在nums.sort()操作之后，为什么可以通过简单的比较nums[i]与nums[i-1]来避免重复的子集？
▷🦆
回溯函数中的终止条件是len(path) == len(nums)，这是否意味着函数只在path与nums长度相同时才停止递归？这样的设计是否必要？
▷🦆
在递归调用backtrace(path, i+1)时，参数i+1的作用是什么？这是否意味着每次递归都是从下一个元素开始？
▷🦆
为什么在path.pop()之后没有再次检查重复元素，这样做是否可能会在后续的递归中产生重复的子集？
▷