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.
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^nSubset with distinct numbers
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
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
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.
Code Implementation
Complexity
Time: O( n* 2^n)
Space: O(n* 2^n)
n: the total number of elements in the given array
