5 months

# 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``, 2``2``, ``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)

See all(3)

Tags

Topics
Related