题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
前言
本题解基于78. 子集的官方题解，请读者在充分理解该题解后继续阅读。
方法1：迭代法实现子集枚举
思路：
代码示例：（Java）
public class Solution1 {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
boolean flag = true;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
flag = false;
break;
}
t.add(nums[i]);
}
}
if (flag) {
ans.add(new ArrayList<Integer>(t));
}
}
return ans;
}
}
复杂度分析
方法2:递归法实现子集枚举
思路：
与方法一类似，在递归时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
代码示例：（Java）
public class Solution2 {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(false, 0, nums);
return ans;
}
public void dfs(boolean choosePre, int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(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);
}
}
复杂度分析
