是否有任何O(n ^ 2)算法来生成数组的所有子序列？

Question

我想知道是否有任何O(n ^ 2)复杂度算法用于生成数组的所有子序列.我知道一个算法,但它需要O((2 ^ n)*n)时间.

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;
    }
}

Answer 1

没有

O(2^n)由于存在O(2^n) 子序列,因此不能存在任何低于复杂度的算法.您需要打印每个,因此时间复杂度必须大于或等于O(2^n).