Grokking Amazon Coding Interview
Vote

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Supreet Sandhu

· 4 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
S

Salah Osman

· 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
Mohammed Dh Abbas

Mohammed Dh Abbas

· 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
Trang Luong

Trang Luong

· a year ago

class Solution:
  # cascading, at each step, add the number to all current subsets
  # If it's a list of list, make sure copy each time or else it will modify reference
  # def find_subsets(self, nums):
  #   subsets = [[]]
  #   #[1, 2, 3]
  #   for num in nums: 
  #     subsets_copy = subsets.copy() # O(n)
  #     for subset in subsets_copy: # O(2^n) (k start with 1 and grow until 2^n for n)
  #       new_subnet = subset.copy() # O(N)
  #       new_subnet.append(num)
  #       subsets.append(new_subnet)
  #   return subsets

  def find_subsets(self, nums):
    result_subsets = []
    self.backtrack(0, [], result_subsets, nums)
    return result_subsets
  # Backtracking solution, building each solution as we go down a tree of decision to build subset
  # backtrack(0, [], [],
Gaurav Thakur

Gaurav Thakur

· 18 days ago

The problem statement does not state to maintain output order. The power set can also be found with dfs/recursion, which can giver order [[],[1],[1,3],[3]] and test fails it.

import java.util.*;

public class Solution {
  List<List<Integer>> subSets = new ArrayList<>();

  public List<List<Integer>> findSubsets(int[] nums) {

    findSets(nums, 0, new ArrayList<Integer>());
    return subSets;
  }

  private void findSets(int[] nums, int curIndex, List<Integer> cur) {
    
    subSets.add(new ArrayList<Integer>(cur));

    for(int i = curIndex; i < nums.length; i++) {
      cur.add(nums[i]);
      findSets(nums, i+1, cur);
      cur.remove(cur.size()-1);
    }
    
  }
}