首页 > 代码库 > LeetCode 90. Subsets II
LeetCode 90. Subsets II
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], []]
【题目分析】
与题目Subset类似，Subsets II中的元素是可能存在重复的。
参考Subset的解法 http://www.cnblogs.com/liujinhong/p/5555139.html
【思路】
为了避免出现重复的解，我们在进行回溯的时候要判断解空间树的当前节点的兄弟节点的值是否相同。我们首先对数组进行排序，然后使用递归回溯法来解决这个问题。
【java代码】
1 public class Solution { 2 public List<List<Integer>> subsetsWithDup(int[] nums) { 3 Arrays.sort(nums); 4 List<List<Integer>> result = new ArrayList<>(); 5 dfs(nums, 0, new ArrayList<>(), result); 6 return result; 7 } 8 9 private void dfs(int[] nums, int idx, List<Integer> path, List<List<Integer>> ret){10 ret.add(path);11 for(int i = idx; i < nums.length; i++){12 if(i > idx && nums[i] == nums[i-1])13 continue;14 List<Integer> p = new ArrayList<>(path);15 p.add(nums[i]);16 dfs(nums, i+1, p, ret);17 }18 }19 }
LeetCode 90. Subsets II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。