Skip to content

Instantly share code, notes, and snippets.

@linminhtoo
Created March 5, 2025 12:54
Show Gist options
  • Save linminhtoo/e8413bac2d2d04e45f98b7d68a034259 to your computer and use it in GitHub Desktop.
Save linminhtoo/e8413bac2d2d04e45f98b7d68a034259 to your computer and use it in GitHub Desktop.
find all subsets
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
'''
DFS
naive solution: choose or don't choose at each index
mental notes:
- empty set [] is always a valid subset
this should naturally arise from the sequence of decisions "don't choose" at every index
'''
res = []
len_nums = len(nums)
def dfs(idx: int, curr_subset: list[int]):
# base case
if idx >= len_nums:
# empty set will be added
res.append(curr_subset)
return
# choose current idx
dfs(idx + 1, curr_subset + [nums[idx]])
# don't choose current idx
dfs(idx + 1, curr_subset)
return
dfs(0, [])
return res
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment