0% completed
Solution: Subsets With Duplicates
.....
.....
.....
Anonymous
· 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
Anonymous
· 2 years ago
Please add a test case for it.
Anonymous
· 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.
Anonymous
· 5 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?
Anonymous
· 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.
Reading Progress
0%