LC090 - Subsets II

Problem

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

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Solution

Backtracking

Do a DFS and backtrack to get all subsets. Time and space complexity is $O(n\cdot 2^n)$.

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
	def dfs(i, subset):
		subsets.append(subset)
		if i == len(nums):
			return
		
		for j in range(i, len(nums)):
			if j > i and nums[j] == nums[j-1]:
				continue
				
			dfs(j + 1, subset + [nums[j]])
	
	subsets = []
	nums.sort()

	dfs(0, [])

	return subsets

Bit Masking

Use bit masking to come up with the power set. Replace pow with bit shift to speed up computation.

Time complexity is still $O(n \cdot 2^n)$ but with a smaller constant time factor than the backtracking solution.

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
	res = set()
	nums.sort()

	for i in range(1 << len(nums)): ## pow(2, len(nums))
		temp = []
		for j in range(len(nums)):
			if i & (1 << j): ##pow(2, j):
				temp.append(nums[j])
		res.add(tuple(temp))
	
	return list(res)