LeetCode 090 Subsets II

LeetCode

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]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10

题目大意：

求所有子集，元素可能相同，不能含相同子集

解题思路：

类似于L078 Subsets，但元素可能相同，所以排序且比较相邻元素，若相等就跳过

解题步骤：

N/A

注意事项：

1. 元素可能相同，所以排序且比较相邻元素，若相等就跳过

Python代码：

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return []
	nums.sort()
	res = [[]]
	self.dfs(nums, 0, [], res)
	return res

def dfs(self, nums, st, path, res):
	if st == len(nums):
		return
	for i in range(st, len(nums)):
		if i > st and nums[i] == nums[i - 1]:
			continue
		path.append(nums[i])
		res.append(list(path))
		self.dfs(nums, i + 1, path, res)
		path.pop()

算法分析：

时间复杂度为O(nx2n)，空间复杂度O(n)