c++ - 从 unordered_set 中获取给定大小 k 的所有子集？

Question

我有一个并且必须为我的集团程序unordered_set<int> vertices生成所有大小的子集。k我见过的所有解决方案（包括 SO 上的所有解决方案）都适用于数组，而不是集合。有没有像 Python 那样itertools.combinations用 C++ 实现的算法？如果没有，我应该怎么做？转换为数组并使用标准算法？我仍然需要在程序中进一步使用集合，所以这会使我的内存需求增加一倍。

标签： c++algorithmsubset

Answer 1

当元素数量变大时，生成所有子集将花费大量时间（除了一些特殊情况，例如从 n 中选择 0、1、n-1 或 n 个元素），所以我不认为加倍内存需求会变成严重的问题，除非你有严格的内存限制。

出于这个原因，我认为您应该将集合转换为数组并应用已知算法。