1. 题目
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subsets-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 示例
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
3. 题解
这题跟子集那个题一样的解法,也是用回溯。但这题多了个限制条件,就是解集不能包含重复的子集,这需要多增加一个sort排序方法和一个HashSet存储即可。
回溯就四步:
1. 确定边界;本题的边界就是当前数组的size与元数组的size一致时就结束,即取到所有元素了。
2. 记录临时数组;当满足条件时,就存储当前数组。本题满足条件是回溯到了最后一个元素,就将临时数组存入到结果数组里面。
3. 取当前元素;将当前元素存入临时数组,然后回溯,一定要记住,回溯之前如果取了元素就要移除去的元素。
4. 不取当前元素;直接回溯;
4. Code
1 public class SubsetsB {
2 public List<List<Integer>> subsetsWithDup(int[] nums) {
3 Set<List<Integer>> ans = new HashSet<>();
4 List<Integer> temp = new ArrayList<>();
5 perm(nums, ans, temp, 0);
6 return new ArrayList<>(ans);
7 }
8
9 public void perm(int[] nums, Set<List<Integer>> ans, List<Integer> temp, int n) {
10 if (n == nums.length) {
11 ans.add(new ArrayList<>(temp));
12 return;
13 }
14 if (temp.size() == nums.length) {
15 return;
16 }
17 // 取当前元素
18 temp.add(nums[n]);
19 perm(nums, ans, temp, n + 1);
20 temp.remove(temp.size() - 1);
21
22 // 不取当前元素
23 perm(nums, ans, temp, n +1);
24 }
25
26 public static void main(String[] args) {
27 int[] nums = {1, 2, 2, 3, 3, 4};
28 System.out.println(new SubsetsB().subsetsWithDup(nums));
29 }
30 }