摘要：题目要求可以先参考关于的这篇博客再看接下来的内容。思路一链表的形式我们可以通过例子，，，来说明。在递归中我们会将起始下标后的值依次加入当前结果集，并将结果集加入结果集数组中。如果遇到重复的数字，则继续遍历下一个数字，直至遍历结束。
题目要求
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
可以先参考关于SubsetI的这篇博客再看接下来的内容。
这里的区别在于假设输入的数组存在重复值，则找到所有不重复的子集。
思路一：链表的形式
我们可以通过例子[1，2，2，3]来说明。当我们遇到重复值时，我们可以使用一个临时数组将所有重复值的结果临时保存起来，在这道题目中就是[[2],[2,2]]，然后再将当前res中的结果和它一一组合成新的结果值，本例子中的当前res为[[ ],[1]]，这样合成之后就是[[],[2],[2,2],[1,2],[1,2,2]]，从而避免产生重复的结果。
代码如下：
public List> subsetsWithDup(int[] nums) {
List> result = new LinkedList>();
result.add(new ArrayList());
int length = nums.length;
Arrays.sort(nums);
for(int i = 0 ; i> temp = new LinkedList>();
for(List tempResult : result){
List copyTemp = new ArrayList(tempResult);
copyTemp.add(nums[i]);
temp.add(copyTemp);
}
i++;
while(i0){
List currentTemp = temp.removeFirst();
result.add(currentTemp);
List moreCurrentTemp = new ArrayList(currentTemp);
moreCurrentTemp.add(nums[i]);
temp.add(moreCurrentTemp);
}
}
result.addAll(temp);
}
return result;
}
思路二：递归
其实对于递归，应当考虑从递归的输入和输出考虑。在这里我们将递归的输入为当前的结果集，当前的数组，和遍历的起始下标。在递归中我们会将起始下标后的值依次加入当前结果集，并将结果集加入结果集数组中。如果遇到重复的数字，则继续遍历下一个数字，直至遍历结束。思路简单清晰，效率也很高。
public List> subsetsWithDup2(int[] nums) {
List> fnl = new ArrayList>();
Arrays.sort(nums);
helper(fnl, new ArrayList(), nums, 0);
return fnl;
}
public void helper(List> fnl, List temp, int[] nums, int start){
fnl.add(new ArrayList(temp));
for(int i =start; istart && nums[i]==nums[i-1]) continue;
temp.add(nums[i]);
helper(fnl, temp, nums, i+1 );
temp.remove(temp.size()-1);
}
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67356.html
