Backtracking: return all possible subsets of unique integer array Python
Tue Aug 09 2022 06:53:38 GMT+0000 (Coordinated Universal Time)
Saved by
@bryantirawan
#python
#depth
#first
#search
#recursive
#neetcode
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []
#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return
#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)
#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)
dfs(0)
return result
content_copyCOPY
https://ibb.co/94Tk6tD shows you binary tree and how array with length of 3 will have 2^3 possible subsets. Because order of subset doesn't matter [2, 3] is same as [3, 2], these are subsets and not permutations.
Comments