Backtracking: return all possible subsets given array with possibly duplicate values python

Tue Aug 09 2022 22:02:17 GMT+0000 (UTC)

Saved by @bryantirawan #python #depth #first #search #recursive #codesignal #climb #list

#solution where you just take subset I and replace last return statement 
class Solution:
    def subsetsWithDup(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) 
        
        #need to remove duplicate sublists within result 
        return ([list(i) for i in {*[tuple(sorted(i)) for i in result]}])  
  

#solution to prevent duplicates in the first place
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

   
        result = []
		nums.sort() 

		def backtrack(i, subset): 
        	if i == len(nums): 
            	res.append(subset.copy())
				return 
			
			#all subsets that include nums[i] 
            subset.append(nums[i]) 
			backtrack(i + 1, subset) 
			#remove number we just added 
            subset.pop()
            
            #all subsets that don't include nums[i]
        	while i + 1 < len(nums) and nums[i] == nums[i + 1]: 
            	i += 1 
			backtrack(i + 1, subset)
		
		backtrack(0, [])
		
		return result 
        
        
        
        
#solution for array with unique integer array. only last return line is dfferent 
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

Very similar to subset I neetcode problem. You can just use that and replace last return statement to remove duplicates or prevent duplicate sublists in the first place. Big O is n2^n Each spot in sublist has 2 choices to include or not to include. How long is each sublist? n so we get n2^n So if you had [1, 2, 2, 3] there will be 12 possible outcomes instead of 2^n = 16 because there are 4 duplicates but 2^n is close enough. If you do naive way of calculating all subsets and then removing duplicates it's still n2^n. Decision tree to prevent duplicates in the first place: https://ibb.co/mbTLtJ1 General concept of preventing duplicates: sort given array. If you skip one number, skip all.

https://leetcode.com/problems/subsets-ii/submissions/