Subsets II

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],
  []
]

Hint: while this question is a little bit tricky compared to Subset. The tricky part is that a same number can be used more than once. Remember that in the previous problem, we use a "bit array" (or an integer, with more or less the same ideas) to indicate whether a number is selected in the subset. In this problem, we can slightly modify it by indicating the number of appearance, assume a number n appears k times in the original array, then this  number can be selected 0, 1, 2, ...k-1, k times. How do we know the number of appearance? In a straightforward way, we can use a hashtable to count and store the numbers. Also, we can sort the input array first, then use an array A[] to store all m distinct numbers from 1..i...m. If the array is sorted, we can use another array number[] to track the number of appearance for each index i, the appearance of A[i].

Java语言: Subsets II

01 public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(num.length<1)
04         return results;
05     Arrays.sort(num);
06     //store unique numbers
07     ArrayList<Integer> number=new ArrayList<Integer>();
08     //store the apprearance of each  number
09     ArrayList<Integer> times=new ArrayList<Integer>();        
10     for(int i=0;i<num.length;i++)
11     {
12         if(number.isEmpty()||number.get(number.size()-1)!=num[i])
13         {
14             number.add(num[i]);
15             times.add(1);
16         }
17         else
18         {
19             int count=times.get(times.size()-1);
20             times.set(times.size()-1,count+1);
21         }
22     }
23     ArrayList<Integer> out=new ArrayList<Integer>();
24     generateSubsets(number, times, out, results,0);
25     return results;  
26 }
27 public void generateSubsets(ArrayList<Integer> number, ArrayList<Integer> times,ArrayList<Integer> out, ArrayList<ArrayList<Integer>>results, int pos)
28 {
29     if(pos==number.size())
30     {
31         ArrayList<Integer> temp=new ArrayList<Integer>(out);
32         results.add(temp);
33         return;
34     }        
35     //get the appearance times of the number at this position
36     int count=times.get(pos);  
37     //do not select the number at current pos
38     //generate subsets recursively from the next position
39     generateSubsets(number, times, out, results, pos+1);  
40     //select the number at current pos from 1 to appearance times
41     for(int i=0;i<count;i++)
42     {
43         //add the current number
44         out.add(number.get(pos));
45         //proceed to the next number recursively
46         generateSubsets(number, times, out, results, pos+1);
47     }
48     //remove all appearances of the current number
49     int size=out.size();
50     for(int i=size-1;i>=size-count;i--)
51     {
52         out.remove(i);
53     }
54 }