Printing contiguous sub-arrays

Question

The following method of printing all subarrays(contiguous subsequences) of an array is faster as compared to the general method of using three nested for loops:

#include <iostream>
#include <vector>

int main()
{
std::vector<int> array;
int N;
std::cin >> N; //size of array

for (int i = 0; i < N; i++) {
int x;
std::cin >> x;
array.push_back(x);
}

 int i = array.size() - 1;
 std::vector<int> subarray=array;

do {
    std::cout << subarray[array.size()-i-1] << " ";

    if (i == 0) {
        subarray.pop_back();

        if (subarray.empty()) {
          array.pop_back();
              subarray=array;
        }

        std::cout << '\n';
        i = subarray.size() - 1;
    } else {
        i--;
    }
    } while (i >= 0);
}

Can the do while loop be optimized further?

Answer 1

Your code has one bug that causes it to crash. The line

std::cout << subarray[array.size()-i-1] << " ";

should instead be

std::cout << subarray[subarray.size()-i-1] << " ";

After the first subarray.pop_back(), the subarray access when i == 0 will go past the end of the subarray.

The major flaw of your code is that it does not print all contiguous subarrays. When I input

4
1 2 3 4

Into your program, I get this output:

1 2 3 4
1 2 3
1 2
1
1 2 3
1 2
1
1 2
1
1

Notice that the subarray 2 3 does not appear. Your program is only faster because it does not finish the job. It needs to be able to print subarrays that do not start with the first element of the original array.

You cannot optimize until your program gives the correct output.