子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
方法一：回溯
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans=new ArrayList<>();
Stack<Integer> stack=new Stack<>();
dfs(0,nums,ans,stack);
return ans;
}
public void dfs(int depth,int[] nums,List<List<Integer>> ans,Stack<Integer> stack) {
if(depth==nums.length){
ans.add(new ArrayList<>(stack));
} else {
dfs(depth+1,nums,ans,stack);
stack.push(nums[depth]);
dfs(depth+1,nums,ans,stack);
stack.pop();
}
}
时间复杂度(n×2n)
空间复杂度(n×2n)
方法二：回溯2
但注意子集2不能用这种方法的set去重
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0, new Stack<>());
return res;
}
private void dfs(int[] nums, int i, Stack<Integer> stack) {
res.add(new ArrayList<>(stack));
for (int j = i; j < nums.length; j++) {
stack.push(nums[j]);
dfs(nums, j + 1, stack);
stack.pop();
}
}
方法三：迭代
最初结果为[]
在遍历nums数组过程中，将结果中的元素取出，在它们后面都加上当前元素
如对于 1 2 3
最初 []
i=0 [],1
i=1 [],1,2,12
i=2 [],1,2,12,3,13,23,123
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans=new ArrayList<>();
ans.add(new ArrayList<>());
for (int i = 0; i < nums.length; i++) {
int size=ans.size();
for (int j=0;j<size;j++){
List<Integer> list = new ArrayList<>(ans.get(j));
list.add(nums[i]);
ans.add(list);
}
}
return ans;
}
时间复杂度O(n×2n)：一共与2n个子集，每个又复制到结果中
空间复杂度O(n×2n)
方法四：迭代利用二进制
原序列中的每个数字ai的状态可能有两种，即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第i位表示 ai是否在子集中。例如，n = 3，a={5,2,9} 时：
0/1 序列 子集 0/1序列对应的二进制数
000 {} 0
001 {9} 1
010 {2} 2
011 {2,9} 3
100 {5} 4
101 {5,9} 5
110 {5,2} 6
111 {5,2,9} 7
可以发现 0/1 序列对应的二进制数正好从 0 到 2n - 1
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < (1 << n); i++) {
List<Integer> list = new ArrayList<>();
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
list.add(nums[j]);
}
}
res.add(list);
}
return res;
}
子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
剪枝
方法一：含有标记数组的回溯
先分析元素不在子集中，再分析在子集中
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
boolean[] used=new boolean[nums.length];
Arrays.sort(nums);
dfs(0, nums, ans, used);
return ans;
}
public void dfs(int depth, int[] nums, List<List<Integer>> ans, boolean[] used) {
if (depth == nums.length) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < used.length; i++) {
if(used[i]){
list.add(nums[i]);
}
}
ans.add(list);
} else {
dfs(depth + 1, nums, ans, used);
if(depth>0&&nums[depth]==nums[depth-1]&&!used[depth-1]){
return;
}
used[depth]=true;
dfs(depth + 1, nums, ans, used);
used[depth]=false;
}
}
另外可以不需要used数组，只需要一个变量记录是否有选前一个元素
private List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(nums, 0, new Stack<>(), false);
return lists;
}
private void dfs(int[] nums, int i, Stack<Integer> stack, boolean used) {
if (i == nums.length) {
lists.add(new ArrayList<>(stack));
return;
}
dfs(nums, i + 1, stack, false);
if (i > 0 && nums[i] == nums[i - 1] && !used) {
return;
}
stack.add(nums[i]);
dfs(nums, i + 1, stack, true);
stack.pop();
}
方法二：不含标记，手工回溯
先分析元素在子集中，再分析在不子集中
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
Arrays.sort(nums);
dfs(0, nums, ans, stack);
return ans;
}
public void dfs(int depth, int[] nums, List<List<Integer>> ans, Stack<Integer> stack) {
if (depth == nums.length) {
ans.add(new ArrayList<>(stack));
} else {
stack.push(nums[depth]);
dfs(depth + 1, nums, ans, stack);
stack.pop();
while (depth+1 < nums.length && nums[depth] == nums[depth + 1]) {
depth++;
}
dfs(depth + 1, nums, ans, stack);
}
}
方法三：迭代
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < (1 << n); i++) {
List<Integer> list = new ArrayList<>();
boolean flag = false;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
if (j > 0 && nums[j] == nums[j - 1] && (i & (1 << (j - 1))) == 0) {
flag = true;
break;
}
list.add(nums[j]);
}
}
if (!flag) {
res.add(list);
}
}
return res;
}
2024更新
使用和组合类似方式
使用used数组
private List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(nums, 0, new Stack<>(), new boolean[nums.length]);
return list;
}
private void dfs(int[] nums, int i, Stack<Integer> stack, boolean[] used) {
list.add(new ArrayList<>(stack));
for (int j = i; j < nums.length; j++) {
if (j > 0 && nums[j] == nums[j - 1] && !used[j - 1]) {
continue;
}
used[j] = true;
stack.push(nums[j]);
dfs(nums, j + 1, stack, used);
stack.pop();
used[j] = false;
}
}
不使用used数组
private List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(nums, 0, new Stack<>());
return list;
}
private void dfs(int[] nums, int i, Stack<Integer> stack) {
list.add(new ArrayList<>(stack));
for (int j = i; j < nums.length; j++) {
if (j > i && nums[j] == nums[j - 1]) {
continue;
}
stack.push(nums[j]);
dfs(nums, j + 1, stack);
stack.pop();
}
}
