Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Subsets With Duplicates (easy)

Problem Statement

Given a set of numbers that might contain duplicates, find all of its distinct subsets.

Example 1:

Input: [1, 3, 3]
Output: [], [1], [3], [1,3], [3,3], [1,3,3]

Example 2:

Input: [1, 5, 3, 3]
Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3], [3,3], [1,3,3], [3,3,5], [1,5,3,3]

Constraints:

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

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gary

· 4 years ago

For example 2, when we sort the input, the results produced are not exactly the same as the output in Example 2 section (under Problem Statement).

For instance, solution code has results like [1, 3, 5] instead of [1, 5, 3]. Are they actually equivalent?

Show 1 reply
L

LeetCoder

· 4 years ago

We should take into account the time needed to sort the array in the over all time complexity , correct ? Looks like we are currently not doing that.

Show 1 reply
H

hj3yoo

· 4 years ago

Nitpick: sorting the array takes O(N*logN) time - can't we keep a hash of previously visited elements instead?

It matters less for this problem as the overall complexity is O(N2^N) which is significantly higher than O(NlogN), but just a food for thought.

Show 2 replies
A

ahonliu

· 2 years ago

Please add a test case for it.

Show 3 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findSubsets(self, nums):
    nums.sort()
    
    subsets = [[]]
    temp = []
    prev_count = 0
    
    # loop through each number
    for index, num in enumerate(nums):
     
      # for non duplicate case. clone previous subsets and append num to each
      if index == 0 or (index > 0 and nums[index] != nums[index - 1]):
        for subset in subsets:
            clone = subset[:]
            clone.append(num)
            temp.append(clone)
      
      # for duplicate case. clone the subsets from the point of prev_count  and append num to each
      else:
        for j in range(len(subsets) - prev_count, len(subsets)):
          clone = list(subsets[j])
          clone.append(num)
          temp.append(clone)
      
      # add the new items to the