Subsets II

---

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:

1. Subsets
2. Letter Case Permutation
3. Find Array Given Subset Sums

Solution:

Java

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);
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  const result = [];
  nums.sort((a, b) => a - b);
  helper(0, nums, [], result, false);
  return result;
};

function helper(index, nums, currentList, result, prevElementSelected) {
  if (index === nums.length) {
    result.push([...currentList]);
    return;
  }

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

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

Python

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        self.helper(0, nums, [], result, False)
        return result

    def helper(self, index: int, nums: List[int], currentList: List[int], result: List[List[int]], prevElementSelected: bool) -> None:
        if index == len(nums):
            result.append(currentList.copy())
            return

        self.helper(index + 1, nums, currentList, result, False)

        if index > 0 and nums[index] == nums[index - 1] and not prevElementSelected:
            return
        currentList.append(nums[index])
        self.helper(index + 1, nums, currentList, result, True)
        currentList.pop()

C++

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        helper(0, nums, {}, result, false);
        return result;
    }
private:
     void helper(int index, const vector<int>& nums, vector<int> currentList, vector<vector<int>>& result, bool prevElementSelected) {
        if (index == nums.size()) {
            result.push_back(currentList);
            return;
        }

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

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

---

Time/Space Complexity:

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

---

Explanation:

It's important to remember solution space size for 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).