Is there any O(n^2) algorithm to generate all sub-sequences of an array?

  • A+
Category:Languages

I was wondering if there is any O(n^2) complexity algorithm for generating all sub-sequences of an array. I know an algorithm but it takes O((2^n)*n) time.

int main() {     int n;      cin >> n;     vector<int> a(n);     for(int i = 0; i < n; ++i)          cin >> a[i];     int64_t opsize = pow(2,n);     for (int counter = 1; counter < opsize; counter++) {         for (int j = 0; j < n; j++) {            if (counter & (1 << j))                  cout << a[j] << " ";         }         cout << endl;     } } 

 


No

There cannot be any algorithm of less than O(2^n) complexity simply because there are O(2^n) sub-sequences. You need to print each of them hence the time complexity has to be greater than or equal to O(2^n).

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: