题目：

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],  []] 题解： 这个在subset题的第一种解法的基础上有两种解决办法。。 1. 在添加res时候判断是否res中已经存过该item了。没存过的才存保证子集唯一性。  代码如下：

 1 

public 

static 

void dfs(

int[] S, 

int start, 

int len, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){

 2         

if(item.size()==len){

 3             

if(!res.contains(item))

 4                 res.add(

new ArrayList<Integer>(item));

 5             

return;

 6         }

 7         

for(

int i=start; i<S.length;i++){

 8             item.add(S[i]);

 9             dfs(S, i+1, len, item, res);

10             item.remove(item.size()-1);

11         }

12 

13     }

14     

15     

public 

static ArrayList<ArrayList<Integer>> subsetsWithDup(

int[] S) {

16         ArrayList<ArrayList<Integer>> res = 

new ArrayList<ArrayList<Integer>> ();

17         ArrayList<Integer> item = 

new ArrayList<Integer>();

18         

if(S.length==0||S==

null)

19             

return res;

20         

21         Arrays.sort(S);

22         

for(

int len = 1; len<= S.length; len++)

23             dfs(S,0,len,item,res);

24             

25         res.add(

new ArrayList<Integer>());

26         

27         

return res;

28     }

2. 还有一种方法就是在DFS过程中 当有重复元素出现就只对当前这个元素走一起，其他重复元素跳过。参考：http://blog.csdn.net/worldwindjp/article/details/23300545 代码如下：

 1 

public 

static 

void dfs(

int[] S, 

int start, 

int len, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){

 2         

if(item.size()==len){

 3             res.add(

new ArrayList<Integer>(item));

 4             

return;

 5         }

 6         

for(

int i=start; i<S.length;i++){

 7             item.add(S[i]);

 8             dfs(S, i+1, len, item, res);

 9             item.remove(item.size()-1);

10             

while(i<S.length-1&&S[i]==S[i+1])

//

跳过重复元素

11 

                i++;

12         }

13 

14     }

15     

16     

public 

static ArrayList<ArrayList<Integer>> subsetsWithDup(

int[] S) {

17         ArrayList<ArrayList<Integer>> res = 

new ArrayList<ArrayList<Integer>> ();

18         ArrayList<Integer> item = 

new ArrayList<Integer>();

19         

if(S.length==0||S==

null)

20             

return res;

21         

22         Arrays.sort(S);

23         

for(

int len = 1; len<= S.length; len++)

24             dfs(S,0,len,item,res);

25             

26         res.add(

new ArrayList<Integer>());

27         

28         

return res;

29     }