Write a method to return all subsets of a set. The elements in a set are pairwise distinct. Note: The result set should not contain duplicated subsets.
Example:
Input: nums = [1,2,3]
Output:
Recursive DFS Algorithm to Generate the Power SubSet
We can do a naive DFS algorithm (Depth First Search) – which will take O(2^N) where N is the length of the given set. For each element, we have two possibilities (choose or skip).
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ans = [] def dfs(left, cur): nonlocal ans if left == len(nums): ans.append(cur) return dfs(left + 1, cur) dfs(left + 1, cur + [nums[left]]) dfs(0, []) return ans |
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
def dfs(left, cur):
nonlocal ans
if left == len(nums):
ans.append(cur)
return
dfs(left + 1, cur)
dfs(left + 1, cur + [nums[left]])
dfs(0, [])
return ansWe have a left cursor and when it reaches the end – we push the current choices into the answer array. There are 
solutions/subsets.
Subsets Algorithms
- Teaching Kids Programming – Finding All Subsets by Bitmasking Algorithm
- Teaching Kids Programming – Finding All Subsets via Backtracking Algorithm (Recursion / Depth First Search)
- Generate the Power SubSet using Depth First Search Algorithm
- Teaching Kids Programming – Cascading Algorithm to Find All Subsets
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
369 wordsloading...
Last Post: Teaching Kids Programming - Recursive Depth First Search Algorithm to Compare Leaf Equivalent Trees
Next Post: Teaching Kids Programming - The Left Side View of Binary Tree via Breadth First Search Algorithm