Subsets Specify a set with individual elements to find all that individual subset.
Input: [1, 3] Output: [], [1], [3], [1,3]
Input: [1, 5, 3] Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]
Solution You can use the breadth-first search (BFS) approach to generate all subsets of the specified set. You can start with an empty set, repeat all the numbers one by one, and add them to the existing set to create a new subset.
As an example, consider [1, 5, 3].
Image diagram
# Time Complexity: O(2^N) where N is the total number of elements in the input set
# Space Complexity: O(2^N)
def find_subsets(nums):
subsets = []
# start by adding the empty subset
subsets.append([])
for currentNumber in nums:
# we will take all existing subsets and insert the current number in them to create new subsets
n = len(subsets)
for i in range(n):
# create a new subset from the existing subset and insert the current element to it
subset = list(subsets[i])
subset.append(currentNumber)
subsets.append(subset)
return subsets
def main():
print("Here is the list of subsets: " + str(find_subsets([1, 3])))
print("Here is the list of subsets: " + str(find_subsets([1, 5, 3])))
main()
Recommended Posts