Friedrich Ewald My Personal Website

Leetcode: All possible subsets

A subset of a list with the elements {a,b,c} is {a,b}. The task is to find all possible subsets. Sets in programming languages are usually not ordered. Therefore, the set {a,b,c} is equivalent to {b,c,a}. The idea for the solution is a nested for-loop that iterates over the results again and again, starting with one empty ([]) result.


The code to solve this problem is listed here.
from typing import List

class Solution:
  def subsets(self, nums: List[int]) -> List[List[int]]:
    n = len(nums)
    output = [[]]

    for num in nums:
      output += [curr + [num] for curr in output]

    return output


Assuming that the input is [1,2,3]. The execution steps look as follows:
# Input
[1, 2, 3]
# Initialization

# First iteration of outer loop
[[], [1]]

# Second iteration of outer loop
# The previously added elements stay in place
[[], [1], [2], [1, 2]]

# Third and final iteration of outer loop
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.