子集 II
题目介绍
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例1：
示例 2：
1
2
| 输入：nums = [0]
输出：[[],[0]]
|
题目解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| package algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubsetsII {
static List<Integer> t = new ArrayList<>();
static List<List<Integer>> ans = new ArrayList<>();
public static List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(false, 0, nums);
return ans;
}
public static void dfs(boolean choosePre, int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
dfs(false, cur + 1, nums);
if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
return;
}
t.add(nums[cur]);
dfs(true, cur + 1, nums);
t.remove(t.size() - 1);
}
public static void main(String[] args) {
int[] nums = new int[]{1,2,2};
System.out.println(subsetsWithDup(nums));
t.clear();
ans.clear();
nums = new int[]{0};
System.out.println(subsetsWithDup(nums));
}
}
|
打印：
思路：
思路上，直接copy了官方的深度递归了。位移的解法实在难以理解。