0090. 子集 II
题目地址(90. 子集 II)
https://leetcode-cn.com/problems/subsets-ii/
题目描述
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例:输入: [1,2,2]输出:[ [2], [1], [1,2,2], [2,2], [1,2], []]前置知识
公司
阿里
腾讯
百度
字节
思路
回溯的基本思路清参考上方的回溯专题。
这道题需要求子集，因此首先我们需要在所有的节点都执行加入结果集的操作，而不是像全排列那样在叶子节点才执行。
另外一个需要注意的是本题是包含重复元素的。以题目中的 [1,2,2] 为例，第一个 2 和第二个 2 是没有区别的。也就是说交换两者的位置也仅算一种情况，而不是多个。
如果是 [1,2,2,2,2,2] 呢？如果还是以 78 题的逻辑来做会有很多重复结果，那么我们如何避免上面的重复计算？
一种可行的方式是先排序，排序之后规定一种针对相邻且相等的情况的取数逻辑，使得无论多少个相邻的同样数字仅有一种取法。
而这个取数逻辑其实很简单，那就是i > start && nums[i] === nums[i - 1]，其中 i 为当前遍历的索引， start 为遍历的起始索引。（大家可以结合上面的回溯专题的图来理解）
关键点解析
回溯法
backtrack 解题公式
代码
语言支持：JS，C++，Python3
JavaScript Code：
function backtrack(list, tempList, nums, start) { list.push([...tempList]); for (let i = start; i < nums.length; i++) { // 和78.subsets的区别在于这道题nums可以有重复 // 因此需要过滤这种情况 if (i > start && nums[i] === nums[i - 1]) continue; tempList.push(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.pop(); }}/** * @param {number[]} nums * @return {number[][]} */var subsetsWithDup = function (nums) { const list = []; backtrack( list, [], nums.sort((a, b) => a - b), 0, [] ); return list;};C++ Code：
class Solution {private: void subsetsWithDup(vector<int>& nums, size_t start, vector<int>& tmp, vector<vector<int>>& res) { res.push_back(tmp); for (auto i = start; i < nums.size(); ++i) { if (i > start && nums[i] == nums[i - 1]) continue; tmp.push_back(nums[i]); subsetsWithDup(nums, i + 1, tmp, res); tmp.pop_back(); } }public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { auto tmp = vector<int>(); auto res = vector<vector<int>>(); sort(nums.begin(), nums.end()); subsetsWithDup(nums, 0, tmp, res); return res; }};Python Code:
class Solution: def subsetsWithDup(self, nums: List[int], sorted: bool=False) -> List[List[int]]: """回溯法，通过排序参数避免重复排序""" if not nums: return [[]] elif len(nums) == 1: return [[], nums] else: # 先排序，以便去重 # 注意，这道题排序花的时间比较多 # 因此，增加一个参数，使后续过程不用重复排序，可以大幅提高时间效率 if not sorted: nums.sort() # 回溯法 pre_lists = self.subsetsWithDup(nums[:-1], sorted=True) all_lists = [i+[nums[-1]] for i in pre_lists] + pre_lists # 去重 result = [] for i in all_lists: if i not in result: result.append(i) return result相关题目
最后更新于
这有帮助吗？