How can I get all subarrays of a given array faster than O(N^2)?

April 8, 2022

I’m trying to print all subarrays of given array like below.

given array : [5,3,2,4,1]
subarray : [
    [5],
    [5,3],
    [5,3,2],
    [5,3,2,4],
    [5,3,2,4,1],
    [3],
    [3,2],
    [3,2,4],
    [3,2,4,1],
    [2],
    [2,4],
    [2,4,1],
    [4],
    [4,1],
    [1]
]

I can print it with nested loops.

But I want to know how to implement it with O(N) or O(2^N).

>Solution :

There are O(n^2) subarrays of an array in the first place.

Printing them — no matter how you generate them — will always take at least O(n^2); you’re always printing at least O(n^2) lines, each of which will take at least O(1).

Finally, since anything O(n^2) is also O(2^n), you already have an algorithm that will work in O(2^n).