King Of Interviews

Subsets II: Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

Try this Problem on your own or check similar problems:

Solution:

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        helper(0, nums, new ArrayList<>(), result, false);
        return result;
    }

    private void helper(int index, int[] nums, List<Integer> currentList, List<List<Integer>> result, boolean prevElementSelected){
        if(index == nums.length){
            result.add(new ArrayList<>(currentList));
            return;
        }

        helper(index + 1, nums, currentList, result, false);

        if(index > 0 && nums[index] == nums[index-1] && !prevElementSelected) return;
        currentList.add(nums[index]);
        helper(index + 1, nums, currentList, result, true);
        currentList.remove(currentList.size() - 1);
    }
}

Time/Space Complexity:

Time Complexity: O(n*2^n)
Space Complexity: O(n)

Explanation:

It’s important to note solution space the problems like permutations/combinations/subsets:

Permutations: N!
Combinations C(n, k) = N!/(N-k)!k!
Subsets: 2^N (element is present or not)

This problem is almost the same as Subsets but with a twist that we have duplicates in the input array and that the result shouldn’t have repeating equal subsets. Generally, your first intuition when someone mentions duplicates should be either hashmap to track repeating elements or sorting the array (giving natural order to the elements, so you can easily check for adjacent duplicates). In this solution we sort the input array before heading to the helper function. We still have the same two choices, take or not take the element. But this time before adding an element we check if it’s equal to the previous element and if the previous element wasn’t selected, we don’t add the current element and return from the function. Why does this guarantee no duplicates in result? Well imagine you have the following sequence 22XYZ if you choose not to take the first element eventually you would have subset 2XYZ (note 2 is the 2nd 2 in the input array), but then you would choose to have the first element and not the second leading to the same subset 2XYZ, so we only choose the second 2 if the first one is chosen too so that could lead us to 2XYZ (second 2 not chosen, first chosen), 22XYZ (both chosen), XYZ (both omitted).

Subsets II