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

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)的限制。