Subsets II
Given a collection of integers that might contain duplicates,S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
IfS=[1,2,2]
,
a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
禁止重复,就使用set,map等容器,就可以很简单解决了。
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S)
{
sort(S.begin(), S.end());
vector<vector<int> > rs(1);
vector<int> temp;
set<vector<int> > us;
us.insert(temp);
for (int i = 0; i < S.size(); i++)
{
for (int j = rs.size()-1; j>=0; j--)
{
temp = rs[j];
temp.push_back(S[i]);
rs.push_back(temp);
us.insert(temp);
}
}
rs.clear();
rs.assign(us.begin(), us.end());
return rs;
}
vector<vector<int> > subsetsWithDup2(vector<int> &S)
{
sort(S.begin(), S.end());
vector<vector<int> > rs(1);
vector<int> temp;
set<vector<int> > us;
us.insert(temp);
for (int i = 0; i < S.size(); i++)
{
for (int j = rs.size()-1; j>=0; j--)
{
temp = rs[j];
temp.push_back(S[i]);
rs.push_back(temp);
us.insert(temp);
}
rs.assign(us.begin(),us.end());
}
return rs;
}
};
//2014-2-14 update
vector<vector<int> > subsetsWithDup(vector<int> &S)
{
sort(S.begin(), S.end());
vector<vector<int> > rs(1);
unordered_set<vector<int> > sv(rs.begin(), rs.end());
for (int i = 0; i < S.size(); i++)
{
for (int j = rs.size() - 1; j >= 0 ; j--)
{
rs.push_back(rs[j]);
rs.back().push_back(S[i]);
sv.insert(rs.back());
}
rs.assign(sv.begin(), sv.end());
}
return rs;
}
分享到:
相关推荐
java代码-LeetCode 217. 存在重复元素
c++ c++_c++编程基础之leetcode题解第40题组合总和II
Leetcode 5个经典元素和问题题解。
1、维护一个哈希表m,存储每个数字上次出现的位置 3、如果nums[i]这个数字,上次出现过,且,出现的位置和现在距离小于k,可以直接返回true 4、遍历结束
java java_leetcode面试题解哈希表第219题存在重复元素II_题解
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
LeetCode去除数组重复元素 Leetcode Leetcode in Cpp Order by Tag 用c++刷leetcode(比较顺手),按照tag顺序,easy & medium Array 0001 Two Sum (Easy) 给定一个数组和一个数字,返回数组中两数之和为给定数字的...
示例 1:输入: [3,2,3]输出: 3示例 2:输入: [2,2,1,1,1,2,2]输出: 2方法一func majorityElement(nums
剑指 Offer II 080. 含有 k 个元素的组合标签:数组、回溯难度:中等题目大意给定两个整数 n 和 k。如果 path 数组的长度等于 k,则将 p
LeetCode去除数组重复元素 algorithms :strawberry:用JavaScript 和 Python 写一些算法 导论 数据结构 排序 JavaScript版 C++版 搜索 字符串 数学 去重 LeetCode 把自己刷过的题写下题解
LeetCode去除数组重复元素 说明 在leetcode上的题目 使用typescript和javaScript语言 先从初级的题目开始,至少一周做一道 依赖 yetm 初级 Two Sum(两数之和) 给定一个整数数组nums和一个目标值 target,请你在该...
leetcode中文版
c++ c++_c++编程基础之leetcode题解第77题组合
leetcode c++ 分类高清版 有答案 leetcode c++ 分类高清版 有答案 leetcode c++ 分类高清版 有答案 leetcode c++ 分类高清版 有答案leetcode c++ 分类高清版 有答案
vs code LeetCode 插件
剑指 Offer II 083. 没有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个不含重复数字的数组 nums 。若未被访问过则将其加入排列中
c++ c++_c++编程基础之leetcode题解第39题组合总和
c++ c++_c++编程基础之leetcode题解第27题移除元素
剑指 Offer II 084. 含有重复元素集合的全排列标签:数组、回溯难度:中等题目大意给定一个可包含重复数字的序列 nums 。解题思路这道题跟「剑指 O
Python python_leetcode面试题解之第77题组合_题解