【leetcode刷题】20T46-子集 II
木又同学2020年第46篇解题报告
leetcode第90题：子集 II
https://leetcode-cn.com/problems/subsets-ii
【题目】
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
【思路】
设置存储当前递归传入的集合，表示子集（称为目前集合），开始遍历的下标start。
从start开始遍历所有元素，如果当前元素和前一个元素相同，则该元素不加入到目前集合进行递归；否则，该元素加入到目前集合，并存入结果，进行递归（开始遍历的下标改为该元素的下标+1）。
举例来说，对于[1, 2, 2]，目前集合为空集[]，开始遍历下标为0
1）遍历第0个元素，目前集合为[1]，设置遍历下标为1，递归遍历（可以得到[1, 2], [1, 2, 2]）；
2）遍历第1个元素，目前集合为[2]，设置变量下标为2，递归遍历（可以得到[2, 2]）；
3）遍历第2个元素，元素和前一个元素相同，不进行递归。
因此，所有可能为[[], [1], [1, 2], [1, 2, 2], [2], [2,2]]。
【代码】
python版本
class Solution(object):
def add_elements(self, nums, start, current, res):
for i in range(start, len(nums)):
if i == start or nums[i] != nums[i - 1]:
tmp = copy.copy(current)
tmp.append(nums[i])
res.append(tmp)
self.add_elements(nums, i + 1, tmp, res)
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
nums.sort()
self.add_elements(nums, 0, [], res)
return res
C++版本
class Solution {
public:
void get_subset(vector<int>& nums, int start, vector<int> current, vector<vector<int>>& res) {
for (int i = start; i < nums.size(); i++) {
if (i == start || nums[i] != nums[i - 1]) {
current.push_back(nums[i]);
res.push_back(current);
get_subset(nums, i + 1, current, res);
current.pop_back();
}
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
vector<int> current;
res.push_back(current);
sort(nums.begin(), nums.end());
get_subset(nums, 0, current, res);
return res;
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读