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

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(num==null) {
            return ret;
        }
        ret.add(new ArrayList<Integer>());
        HashSet<String> keys = new HashSet<String>();
        for(int i=0;i<num.length;i++) {
            int s = num[i];
            ArrayList<ArrayList<Integer>> add = new ArrayList<ArrayList<Integer>>();
            for(ArrayList<Integer> lst : ret) {
                ArrayList<Integer> lst2 = new ArrayList<Integer>(lst);
                lst2.add(s);
                add.add(lst2);
            }
            for(ArrayList<Integer> lst : add) {
                StringBuilder sb = new StringBuilder();
                for(Integer in : lst) {
                    sb.append(in.intValue()).append("_");
                }
                if(!keys.contains(sb.toString())) {
                    ret.add(lst);
                    keys.add(sb.toString());
                }
            }
        }
        return ret;
        
    }
}

=========================

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return ret;
        }
        Arrays.sort(nums);
        helper(nums, 0, new ArrayList<Integer>(), ret);
        return ret;
    }
    
    private void helper(int[] nums, int cur, List<Integer> curList, List<List<Integer>> ret) {
        List<Integer> newList = new ArrayList<Integer>(curList);
        ret.add(newList);
        for (int i = cur; i < nums.length; i++) {
            curList.add(nums[i]);
            helper(nums, i + 1, curList, ret);
            curList.remove(curList.size() - 1);
            while (i != nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
    }
}

=========

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        helper(nums, 0, new ArrayList<>(), res);
        return res;
    }
    
    private void helper(int[] nums, int cur, List<Integer> list, List<List<Integer>> res) {
        List<Integer> newList = new ArrayList<>(list);
        res.add(newList);
        for (int i = cur; i < nums.length; i++) {
            if (i != cur && nums[i] == nums[i - 1]) continue;
            list.add(nums[i]);
            helper(nums, i + 1, list, res);
            list.remove(list.size() - 1);
        }
    }
}