如何生成一个集合的所有唯一子集？

Question

最近我遇到了一个算法问题，它要求从给定的集合中生成唯一的子集。 假设集合为 S={1, 2, 3, 4}其中n=4（元素数量）。 然后结果应该生成所有的子集： - {（1,2），（1,3），（1,4），（2,3），（2,4），（3,4）}

#include<iostream> 
int main() 
{ 
int k; 
std::cin>>k; 
for(long int i=1;i<=k;i++) 
{ 
    for(long int j=i+1;j<=k;j++) 
    { 
     std::cout<<i<<" "<<j<<"\n"; 
    } 
} 
return 0; 
} 

我有一个为O（n^2）的方法，但该合同引起的当数大 对于n = 1000需要花费大量的时间，因为它必须产生499,500元的问题！

有没有人有更好的解决方案复杂性明智？算法将不胜感激！

Answer 1

一组大小为n的子集的数量是2^n。在这里，可能只有大小为2的子集被询问。因此，这些子集的数量是n*(n-1)/2。

由于每个集合都是唯一的，为了生成它们，至少需要进行许多计算。

因此，对于这些情况，最小复杂度受这些数字Ω(n^2) and Ω(2^n)的限制。