Link: https://leetcode.com/problems/subsets-ii/

Constaint:

The array may contains duplicate.
The array may not be sorted.

Idea

The idea is to think about how to avoid adding duplicate values to the subset. We will process the first occurance of a number (nums[i]) as it is in Subsets I problem, but all the subsequent occurances j, where j > i && nums[j] == nums[i], will be skipped if nums[i] is absent from the subset. Or put it another way, given an array [a, b, b', c], we don't add b' to the subset if: (b = b' && b is NOT in the subset).

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(nums);
        search(nums, 0, new ArrayList<Integer>(), results);
        return results;
    }
    
    private void search(int[] nums, int index, List<Integer> subset, List<List<Integer>> results) {
        if (nums.length == index) {
            results.add(new ArrayList<Integer>(subset));
            return;
        }
        
        subset.add(nums[index]);
        search(nums, index + 1, subset, results);
        subset.remove(subset.size() - 1);
        while (index + 1 < nums.length && nums[index] == nums[index + 1] ) {
            index++;
        }
        
        search(nums, index + 1, subset, results);
    }
}

Reference: https://leetcode.com/problems/subsets-ii/discuss/30150/Very-simple-and-fast-java-solution