Java for LeetCode 090 Subsets II

浏览数：104 / 时间：2015年06月08日

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
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],
  []
]

解题思路一：

偷懒做法，将Java for LeetCode 078 Subsets中的List换为Set即可通过测试，JAVA实现如下：

public List<List<Integer>> subsetsWithDup(int[] nums) {
	    Set<List<Integer>> list = new HashSet<List<Integer>>();
	    list.add(new ArrayList<Integer>());
	    Arrays.sort(nums);
	    for(int i=1;i<=nums.length;i++)
	        dfs(list, nums.length, i, 0,nums,-1);
	    return new ArrayList(list);
	}
	 
	static List<Integer> alist = new ArrayList<Integer>();
	 
	static void dfs(Set<List<Integer>> list, int n, int k, int depth,int[] nums,int last) {
	    if (depth >= k) {
	        list.add(new ArrayList<Integer>(alist));
	        return;
	    }
	    for (int i = last+1; i <= n-k+depth; i++) {
	        alist.add(nums[i]);
	        dfs(list, n, k, depth + 1,nums,i);
	        alist.remove(alist.size() - 1);
	    }
	}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 090 Subsets II