Skip to main content

Subsets

Question​

Given a set of distinct integers, generate all possible subsets (the power set).

Example 1
Input: [1,2,3]

Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2]
]

Solution​

all//Subsets.py


def subsets(nums):
    result = [[]]
    for num in nums:
        # for each element in the array, we will create a new set of subsets
        # by adding the element to all the existing subsets
        new_subsets = []
        for subset in result:
            # create a new subset by adding the element to the existing subset
            new_subset = subset + [num]
            new_subsets.append(new_subset)
        # add the new subsets to the result
        result.extend(new_subsets)
    return result

# test
nums = [1,2,3]
print(subsets(nums))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]