第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0090. 子集 II

题目地址(90. 子集 II)

题目描述

1
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
2
3
说明:解集不能包含重复的子集。
4
5
示例:
6
7
输入: [1,2,2]
8
输出:
9
[
10
[2],
11
[1],
12
[1,2,2],
13
[2,2],
14
[1,2],
15
[]
16
]
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

回溯的基本思路清参考上方的回溯专题。
这道题需要求子集,因此首先我们需要在所有的节点都执行加入结果集的操作,而不是像全排列那样在叶子节点才执行。
另外一个需要注意的是本题是包含重复元素的。以题目中的 [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:
1
function backtrack(list, tempList, nums, start) {
2
list.push([...tempList]);
3
for (let i = start; i < nums.length; i++) {
4
// 和78.subsets的区别在于这道题nums可以有重复
5
// 因此需要过滤这种情况
6
if (i > start && nums[i] === nums[i - 1]) continue;
7
tempList.push(nums[i]);
8
backtrack(list, tempList, nums, i + 1);
9
tempList.pop();
10
}
11
}
12
/**
13
* @param {number[]} nums
14
* @return {number[][]}
15
*/
16
var subsetsWithDup = function (nums) {
17
const list = [];
18
backtrack(
19
list,
20
[],
21
nums.sort((a, b) => a - b),
22
0,
23
[]
24
);
25
return list;
26
};
Copied!
C++ Code:
1
class Solution {
2
private:
3
void subsetsWithDup(vector<int>& nums, size_t start, vector<int>& tmp, vector<vector<int>>& res) {
4
res.push_back(tmp);
5
for (auto i = start; i < nums.size(); ++i) {
6
if (i > start && nums[i] == nums[i - 1]) continue;
7
tmp.push_back(nums[i]);
8
subsetsWithDup(nums, i + 1, tmp, res);
9
tmp.pop_back();
10
}
11
}
12
public:
13
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
14
auto tmp = vector<int>();
15
auto res = vector<vector<int>>();
16
sort(nums.begin(), nums.end());
17
subsetsWithDup(nums, 0, tmp, res);
18
return res;
19
}
20
};
Copied!
Python Code:
1
class Solution:
2
def subsetsWithDup(self, nums: List[int], sorted: bool=False) -> List[List[int]]:
3
"""回溯法,通过排序参数避免重复排序"""
4
if not nums:
5
return [[]]
6
elif len(nums) == 1:
7
return [[], nums]
8
else:
9
# 先排序,以便去重
10
# 注意,这道题排序花的时间比较多
11
# 因此,增加一个参数,使后续过程不用重复排序,可以大幅提高时间效率
12
if not sorted:
13
nums.sort()
14
# 回溯法
15
pre_lists = self.subsetsWithDup(nums[:-1], sorted=True)
16
all_lists = [i+[nums[-1]] for i in pre_lists] + pre_lists
17
# 去重
18
result = []
19
for i in all_lists:
20
if i not in result:
21
result.append(i)
22
return result
Copied!

相关题目