LeetCode90. 子集 II
image
升级版子集问题，最简单的办法，先把所有元素存储到set中去重，然后再重新赋值给数组，再dfs，但这样做太简单了，没什么难度，于是换了一种做法，不去重，直接dfs
class Solution {
public static List<List<Integer>> ans = new ArrayList<List<Integer>>();
public static boolean[] v = new boolean[100];
public static void dfs(int idx,int[] nums) {
//[1,2,2]
if(idx >= nums.length) {
List<Integer> tmp = new ArrayList<Integer>();
for(int i = 0;i < nums.length;i++)
if(v[i])
tmp.add(nums[i]);
ans.add(tmp);
return;
}
if(idx > 0 && nums[idx - 1] == nums[idx] && !v[idx - 1]) {
v[idx] = false;
dfs(idx + 1,nums);//no
} else {
v[idx] = true;
dfs(idx + 1,nums);//yes
v[idx] = false;
dfs(idx + 1,nums);//no
}
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
ans.clear();
int n = nums.length;
for(int i = 0;i < n;i++)
for(int j = i + 1;j < n;j++)
if(nums[j] > nums[i]) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
dfs(0,nums);
return ans;
}
}dfs函数前面都是正常的套路了，主要是后面的判断，如果前面元素的值和我当前搜索到的值一样，并且前面的那个数值没选过，那我这次就选。 举个例子，假设有数组[2,2,2,2,2]，以0表示不选，1表示选，那么可能的情况就有[1,0,0,......],[1,1,0,......]......，但是绝对不能出现[0,1,...]这种[0,1]序列，因为会和[1,0...]这种序列重复，所以当上一个值没选，那么当前的值如果和它相同，当前的值也不能选，对应的就是这段代码片：
if(idx > 0 && nums[idx - 1] == nums[idx] && !v[idx - 1]){
v[idx] = false;
dfs(idx + 1,nums);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读