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 Complexity: O(2N) since, in each step, the number of subsets doubles.
Space Complexity: O(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
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)
