Leetcode 90 - Subsets II（Search）

2019-11-08 03:06:24

字体：大中小

来源：转载

供稿：网友

题意

生成一个数组的所以子集。

思路

和之前的subsets一样，但是关键问题是要去重。

算法1

很暴力，用一个set套一个multiset来判断当前结果是否出现过。

算法2

我们先将数组排序，然后开始考虑怎么去重。

在含有重复元素的时候，如果当前数和前面一个数相同的时候：当前仅当前面的一个数使用时，当前数字才能使用。

于是，我们添加一个use数组来记录某位置是否访问。

算法3

不用use数组直接跳过相同的元素。

代码

//algorithm 1class Solution {PRivate: set<multiset<int>> has; vector<vector<int>> ans;public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { int n = nums.size(); for (int s = 0; s < (1 << n); s++) { vector<int> v; multiset<int> hs; for (int i = 0; i < n; i++) { if (s & (1 << i)) { v.push_back(nums[i]); hs.insert(nums[i]); } } if (has.find(hs) == has.end()) { ans.push_back(v); has.insert(hs); } } return ans; }};//algorithm 2class Solution {public: vector<vector<int>> ans; vector<int> a; void dfs(int pos, vector<int>& use, vector<int>& v) { if (pos == a.size()) { ans.push_back(v); return; } dfs(pos + 1, use, v); if (pos && a[pos] == a[pos - 1]) { if (use[pos - 1]) { use[pos] = 1; v.push_back(a[pos]); dfs(pos + 1, use, v); v.pop_back(); use[pos] = 0; } } else { use[pos] = 1; v.push_back(a[pos]); dfs(pos + 1, use, v); v.pop_back(); use[pos] = 0; } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); a = nums; vector<int> use(nums.size(), 0); vector<int> v; dfs(0, use, v); return ans; }};//algorithm 3class Solution {private: vector<vector<int>> ans;public: void dfs(vector<int>& v, vector<int>& a, int pos) { ans.push_back(v); for (int i = pos; i < a.size(); i++) { v.push_back(a[i]); dfs(v, a, i + 1); v.pop_back(); while (a[i] == a[i + 1]) i++; } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<int> v; dfs(v, nums, 0); return ans; }};

上一篇：判断n 是不是素数

下一篇：笔试题（带答案）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注