- 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)`

.