Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Subsets

Problem Statement

Given a set with distinct elements, find all of its distinct subsets.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

About the output order. Produce the subsets in the order the examples show: start with the empty subset, then take each number in input order and extend all existing subsets with it

.....

.....

.....

Like the course? Get enrolled and start learning!
Gaurav Thakur

Gaurav Thakur

· a month 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);
    }
    
  }
}
Show 1 reply
Trang Luong

Trang Luong

· 2 years 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, [], [],
Show 1 reply
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
Show 1 reply
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
S

Supreet Sandhu

· 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