Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Subsets With Duplicates

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

Why this is a Subsets problem

What the question saysThe signal it matches
"find all of its distinct subsets"you must produce all subsets

.....

.....

.....

Like the course? Get enrolled and start learning!
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
Show 1 reply
A

ahonliu

· 2 years ago

Please add a test case for it.

Show 3 replies
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
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
H

hj3yoo

· 5 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

Reading Progress

0%

Vote for new content