Subsets II

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

Note:The solution set must not contain duplicate subsets.

For example,
Ifnums=[1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        ArrayList<List<Integer>> ans = new ArrayList<>();

        Arrays.sort(nums);
        dfs(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans) {

        ans.add(new ArrayList<>(sub));

        for(int i = start; i < nums.length; i ++) {

            if(i > start && nums[i-1] == nums[i]) continue;
            sub.add(nums[i]);
            dfs(nums, i + 1, sub, ans);
            sub.remove(sub.size() - 1);
        }
    }
}

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        ArrayList<List<Integer>> ans = new ArrayList<>();

        int start = 0;
        int count = 0;
        ans.add(new ArrayList<>());

        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i ++) {

            if(i > 0 && nums[i-1] == nums[i])
                start = count;
            else
                start = 0;

            count = ans.size();
            for(int j = start; j < count; j ++) {
                List<Integer> tmp = new ArrayList<>(ans.get(j));
                tmp.add(nums[i]);
                ans.add(new ArrayList<>(tmp));
            }
        }

        return ans;
    }
}