[LeetCode 90] Subsets II

题目链接：subsets-ii

[java] view plain copy

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

/**

*

Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

*

*/

public class SubsetsII {

//  19 / 19 test cases passed.

//  Status: Accepted

//  Runtime: 259 ms

//  Submitted: 0 minutes ago

//时间复杂度O(2^n) 空间复杂度 O(n)

//偷懒了，直接用了set容器，去除重复子集

public Set<List<Integer>> subsets = new HashSet<List<Integer>>();

public List<List<Integer>> subsetsWithDup(int[] num) {

Arrays.sort(num);

subsets(num, 0, new ArrayList<Integer>());

return new ArrayList<List<Integer>>(subsets);

}

public void subsets(int[] S, int step, List<Integer> subset) {

if(step == S.length) {

subsets.add(subset);

return;

}

//num[step] 不加入子集中

subsets(S, step + 1, new ArrayList<Integer>(subset));

//num[step] 加入子集中

subset.add(S[step]);

subsets(S, step + 1, new ArrayList<Integer>(subset));

}

public static void main(String[] args) {

// TODO Auto-generated method stub

}

}