1 month

Coding Patterns: Subsets




Set A is said to be a subset of Set B if all the elements of Set A are also present in Set B. In other words, set A is contained inside Set B. 

The subsets of any set consists of all possible sets including its elements and the null set.

Example: Find all the subsets of set A = {1,2,3,4}                                        

Subsets = {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3},{2,4}, {3,4}, {1,2,3}, {2,3,4}, {1,3,4}, {1,2,4}, {1,2,3,4}

Subsets pattern is very useful to solve problems involve dealing with permutations and combinations of a given set of elements. Python provides direct methods to find permutations and combinations of a sequence. These methods are present in itertools package.

from itertools import permutations                            

# Get all permutations of [4, 6 8] 

perm = permutations([4, 6, 8])                                 

 

# Get all permutations of length 3  

perm = permutations([11, 22, 32,41], 3)                                 

It generates nCr * r! permutations if the length of the input sequence is n and the input parameter is r.

# A Python program to print all  combinations of given length

from itertools import combinations                                                              

# Get all combinations of [71, 17,22, 83] # and length 3

comb = combinations([71, 17,22,83], 3)                            

Combinations are emitted in the lexicographic sort order of input. So, if the input list is sorted, the combination tuples will be produced in sorted order. 

If we want to make a combination of the same element to the same element then we use combinations_with_replacement. 

from itertools import combinations_with_replacement                          

# Get all combinations of [1, 2, 3] and length 2 

comb = combinations_with_replacement([1, 2, 3], 2)              

This pattern describes an efficient Breadth First Search (BFS) approach to handle all these problems.

LeetCode 704 - Binary Search [easy]

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:   Input: nums = [1,2,3]        Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 

Solution 1:                                                                                      

class Solution:                                                                              
    def subsets(self, nums: List[int]) -> List[List[int]]:                      
        result = [[]]                                                                             
        for num in nums:                                                                  
            result += [item + [num] for item in result]                         
        return result                                                                         

Time ComplexityO(2N) since, in each step, the number of subsets doubles.

Space ComplexityO(2N)                                                                            

Solution 2:                                                                                            

from itertools import combinations                                                    
class Solution:                                                                                   
    def subsets(self, nums: List[int]) -> List[List[int]]:                           
        ans=[]                                                                                        
        for i in range(len(nums)+1):                                                           
            ans.extend(combinations(nums,i))                                        
        return ans                                                                                 

LeetCode 90. Subsets II

 

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:    Input: nums = [1,2,2]     Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Solution 1:                                                                                    

class Solution:                                                                        
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        results = []                                                                      
        nums = sorted(nums)                                                     

        self.helper(results, [], 0, nums)                                      
        return results                                                                 
    def helper(self, results, combination, start, nums):             
        if combination not in results:                                              
            results.append(list(combination))                               
        for i in range(start, len(nums)):                                     
            combination.append(nums[i])                                  
            self.helper(results, combination, i + 1, nums)            
            combination.pop()                                                    

Solution 2:                                                                              

class Solution:                                                                    
    def subsetsWithDup(self, nums):                                 
        ret = []                                                                             
        self.dfs(sorted(nums), [], ret)                                       
        return ret                                                                   
    def dfs(self, nums, path, ret):                                       
        ret.append(path)                                                    
        for i in range(len(nums)):                                           
            if i > 0 and nums[i] == nums[i-1]:                           
                continue                                                             
            self.dfs(nums[i+1:], path+[nums[i]], ret)                
        

 

 


Responses(0)







Related