Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Subsets

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:
  def find_subsets(self, nums):
    
    subsets = [[]]
    temp = []
    
    for num in nums:
      
      for subset in subsets:
        clone = subset[:]
        clone.append(num)
        temp.append(clone)
      
      for item in temp:
        subsets.append(item)
      temp = []
    return subsets
A

Anonymous

· 4 years ago

Could I get clarification on the space complexity? Returned output list is O(n), and the subsets take up 2^n resulting in O(n*2^n)

So [1,2...] -> [[],[1],[2],[1,2]....]

Show 2 replies
A

Anonymous

· 5 years ago

I dint understand how's the time complexity of creating subsets is O(N*2^N). Can someone please help me understanding? Thanks!

Show 4 replies

Reading Progress

0%

Vote for new content