用C++的STL的set可以解决子集问题吗?
就是找到所有的子集
不知道你需要的是不是这种
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
set<vector<int>> se;
for(auto x : nums) {
set<vector<int>> temp;
for(auto c : se) {
auto k = c;
k.push_back(x);
temp.insert(k);
}
temp.insert({x});
se.insert(temp.begin(),temp.end());
}
vector<vector<int>> ve;
ve.push_back({});
for(auto c : se) {
ve.push_back(c);
}
return ve;
}
仅供参考:
#include <vector>
#include <iostream>
void BackTrackSubArrays(std::vector<char> &vecTemp, size_t &nCount, size_t nTotal, size_t nBegin, const std::vector<char> &vecArray)
{
if (vecTemp.size() == nTotal)
{
++nCount;
return;
}
for (size_t i = nBegin; i < vecArray.size(); i++)
{
vecTemp.push_back(vecArray[i]);
BackTrackSubArrays(vecTemp, nCount, nTotal, i + 1, vecArray);
vecTemp.pop_back();
}
}
void SubArrays(const std::vector<char> &vecArray)
{
std::vector<char> vecTemp;
vecTemp.reserve(vecArray.size());
size_t nCount = 0;
for (size_t i = 0; i <= vecArray.size(); i++)
{
BackTrackSubArrays(vecTemp, nCount, i, 0, vecArray);
std::cout << "长度为" << i << "的子集有:" << nCount << "个" << std::endl;
nCount = 0;
}
}
int main()
{
SubArrays({ 'A','D','F','Z','K','L','O' }); //此处用到c++11的初始化语法,如果编译器不支持c++11,请自己构造std::vector<char>输入
return 0;
}
//长度为0的子集有:1个
//长度为1的子集有:7个
//长度为2的子集有:21个
//长度为3的子集有:35个
//长度为4的子集有:35个
//长度为5的子集有:21个
//长度为6的子集有:7个
//长度为7的子集有:1个
//