Problem
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
问题
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明: 解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路
回溯
在 LeetCode 0070 题基础上,判断当前元素是否和前一个元素相同,相同就剪枝。
Python3 代码
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
# 先对 nums 进行排序
nums.sort()
def backtrack(nums, start, path):
# 加入 res
res.append(path)
# i 从 start 开始递增
for i in range(start, n):
# 剪枝:当前元素和前一个元素相同
if i > start and nums[i - 1] == nums[i]:
continue
# 回溯及更新 path
# path.append([nums[i]])
backtrack(nums, i + 1, path + [nums[i]])
# path.pop()
backtrack(nums, 0, [])
return res