[LeetCode] Subsets II
Subsets II Given a collection of integers that might contain duplicates, nums, 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, If nums =
問題解決の考え方:
重さを落とすとsetで記録します.列挙すると、バイナリインクリメントして列挙することができます.iは0から2^n−1にインクリメントされ、iのバイナリ表現で対応するビットが1であれば項目に追加される.
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example, If nums =
[1,2,2]
, a solution is: [
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
問題解決の考え方:
重さを落とすとsetで記録します.列挙すると、バイナリインクリメントして列挙することができます.iは0から2^n−1にインクリメントされ、iのバイナリ表現で対応するビットが1であれば項目に追加される.
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
set<vector<int>> contains; //
std::sort(nums.begin(), nums.end());
int num = 1 << nums.size();
for(int i=0; i<num; i++){
int flag = i;
int j=0;
vector<int> item;
while(flag!=0){
if(flag&0x1==1){
item.push_back(nums[j]);
}
flag = flag>>1;
j++;
}
if(contains.find(item)==contains.end()){
contains.insert(item);
result.push_back(item);
}
}
return result;
}
};