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.
Solution
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 outputExample
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]]