Backtracking: return all possible subsets of unique integer array Python

PHOTO EMBED

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.