セットのすべてのユニークなサブセットを生成するにはどうすればいいですか？

Question

最近、私は与えられたセットからユニークなサブセットを生成するように求めるアルゴリズム上の問題に遭遇しました。 セットが S={1, 2, 3, 4}の場合、n=4（要素数）とします。 結果はすべてn*(n-1)/2 のサブセットを生成するはずです。 - {（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）のアプローチを持っていますが、数字は、それは499500個の要素を生成しなければならなかったので、それは多くの時間を要し、N = 1000のため 大きい場合に生じる問題があります！

誰にでもより優れたソリューションの複雑さがありますか？アルゴリズムが評価されるだろう！

Answer 1

サイズnのサブセットの数は2^nです。ここではおそらく、サイズが2のサブセットのみが尋ねられます。したがって、そのようなサブセットの数はn*(n-1)/2です。

これらのセットのそれぞれは固有であるため、それらを生成するには、少なくとも多くの計算が必要です。

したがって、最小の複雑さは、これらの場合、これらの数値Ω(n^2) and Ω(2^n)によって制限されます。