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

Iterative Version
Code from http://www.programcreek.com/2013/01/leetcode-subsets-ii-java/

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { if (num == null) return null; Arrays.sort(num); ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>(); for (int i = num.length-1; i >= 0; i--) { //get existing sets if (i == num.length - 1 || num[i] != num[i + 1] || prev.size() == 0) { prev = new ArrayList<ArrayList<Integer>>(result); } //add current number to each element of the set for (ArrayList<Integer> temp : prev) { temp.add(0, num[i]); } //add each single number as a set, only if current element is different with previous if (i == num.length - 1 || num[i] != num[i + 1]) { ArrayList<Integer> temp = new ArrayList<Integer>(); temp.add(num[i]); prev.add(temp); } //add all set created in this iteration result.addAll(prev); } //add empty set result.add(new ArrayList<Integer>()); return result; }

Recursive Version
Code from http://shanjiaxin.blogspot.com/2014/02/subsets-ii-leetcode.html

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

  Arrays.sort(num);

  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

  ArrayList<Integer> list = new ArrayList<Integer>();

  subsetsWithDupHelper(result, list, num, 0);

  return result;

 }

 private static void subsetsWithDupHelper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] num, int position) {

  result.add(new ArrayList<Integer>(list));

  for (int i = position; i < num.length; i++) {

   if (i != position && num[i] == num[i-1]){

    continue;

   }   

   list.add(num[i]);

   subsetsWithDupHelper(result, list, num, i+1);

   list.remove(list.size() - 1);

  }

 }

Code from http://jelices.blogspot.com/2014/03/leetcode-subsets-ii.html

public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        subsetsWithDup(num, 0, new ArrayList<Integer>(), solution);
        return solution;
    }
    
    public void subsetsWithDup(int[] num, int index, ArrayList<Integer> tempSolution, List<List<Integer>> solution) {
        if(index == num.length)
        {
            solution.add((List<Integer>)tempSolution.clone());
            return;
        }
        
        //Do not add element num[i]
        int value = num[index];
        int i= index;
        while(i<num.length && num[i]==value)
            i++;
        subsetsWithDup(num, i, tempSolution, solution);
            
        //Add element num[i]
        tempSolution.add(num[index]);
        subsetsWithDup(num, index+1, tempSolution, solution);
        tempSolution.remove(tempSolution.size()-1);
    }

Code from http://fisherlei.blogspot.com/2013/01/leetcode-subsets-ii.html
vector<vector<int> > subsetsWithDup(vector<int> &S) {
  vector<vector<int> > result;
  vector<int> output;  
  if(S.size() ==0) return result;
  result.push_back(output);
  sort(S.begin(), S.end());
  generateSub(S, 0, result, output);
}
void generateSub(vector<int> &s, int step, vector<vector<int> > &result, vector<int>& output)
{        
  for(int i = step;i<s.size(); i++ )
  {
output.push_back(s[i]);
result.push_back(output);
if(i< s.size()-1)
 generateSub(s, i+1, result, output);
output.pop_back();
while(i<s.size()-1 && s[i] == s[i+1])
 i++;
  }    
}
Also refer to http://codeganker.blogspot.com/2014/04/subsets-ii-leetcode.html
Read full article from My Own Notes: Leetcode: Subsets II