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

subset2.java

// https://www.interviewbit.com/problems/subsets-ii/

import java.util.*;

import java.util.ArrayList;
import java.util.Collections;

public class Solution {

    public static void main(String[] args) {
        Solution x = new Solution();
        ArrayList<Integer> l = new ArrayList<Integer>();
        l.add(1);
        l.add(2);
        l.add(2);
        System.out.println(x.subsets(l));
    }

    public Set<ArrayList<Integer>> subsets(ArrayList<Integer> a) {
        Set<ArrayList<Integer>> output = new HashSet<ArrayList<Integer>>();
        output.add(new ArrayList<Integer>());
        if (a.size() == 0) {
            return output;
        }
        Collections.sort(a);
        generate(a, output, new ArrayList<Integer>(), 0);
        return output;
    }

    public void generate(ArrayList<Integer> a, Set<ArrayList<Integer>> output,
                         ArrayList<Integer> temp, int index) {
        for (int i = index; i < a.size(); i++) {
            temp.add(a.get(i));
            output.add(new ArrayList<Integer>(temp));
            generate(a, output, temp, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}