Interview Bootcamp
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.

Solution

To generate all subsets of the given set, we can use the Breadth First Search (BFS) approach. We can start with an empty set, iterate through all numbers one-by-one, and add them to existing sets to create new subsets

.....

.....

.....

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

· 20 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);
    }
    
  }
}