Subsets

To find all possible subsets in a given array, sort the array if the array contains duplicate numbers. Iterate through all numbers and add them to the existing subsets to create new subsets. However, if a number is duplicated in the array, only add it to the subsets which were created in the previous step.

subsets summary card

Table of Contents
· Subets
· Subset with distinct numbers
  ∘ Graphical Explanation
  ∘ Code Implementation
  ∘ Complexity
    ∘ Golang
    ∘ Python
· Subset with duplicate numbers
  ∘ Graphical Explanation
  ∘ Code Implementation
  ∘ Complexity
    ∘ Golang
    ∘ Python

Subets

Given an array of n distinct elements, the total number of subsets is 2^n. For each element, we can have two choices, include or not include.

subsets: 2^n

Subset with distinct numbers

LeetCode 78: Subsets

Iterate through all numbers and add them to the existing subsets to create new subsets.

Graphical Explanation

• step1: Initialize subsets with an empty set

subsets = [[]]

• step2: Iterate through all numbers and add them to the existing subsets to create new subsets

subset with distinct numbers

Code Implementation

Complexity

Time: O( n* 2^n)
Space: O(n* 2^n)
n: the total number of elements in the given array

Golang

Python

Subset with duplicate numbers

LeetCode 90: Subsets II

Sort the input array to allow duplicate numbers to be next to each other and then iterate through all numbers. If the number is duplicated, only add it to the subsets which were created in the previous step.

Graphical Explanation

• step1: Sort the input array
• step2: Initialize subsets with an empty set

subsets = [[]]

• step3: Set startIdx and endIdx to 0

startIdx, endIdx: remember created subsets in the previous step

• step4: Iterate through all numbers and add them to the existing subsets to create new subsets.

If the number is duplicated, only add it to the subsets which were created in the previous step.

subset with duplicates

Code Implementation

Complexity

Time: O( n* 2^n)
Space: O(n* 2^n)
n: the total number of elements in the given array

Golang

Python

You can access the source code here.

LeetCode Problems:

• 78. Subsets
• 90. Subsets II