Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Subsets (easy)

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.

Try it yourself

Try solving this question here:

.....

.....

.....

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

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