Recursion: Given an array, generate all sub arrays using recursion

Problem Statement:

You are given an array, you need to generate all sub arrays of the given array

Example:

Input:

arr = {1, 2, 3}

Output:

[1], [1, 2], [2], [1, 2, 3], [2, 3], [3]

Solution 1: Iterative Approach

Start from the index 0 and run till n-1.

For each index i, start from i to n-1 in the nested loop.

Then print the elements respectively

Solution 2: Recursive Approach

In this approach, take 2 pointers,start and end.

Follow below steps:

Base case: if end pointer points to the array size, then return

Increment end of start becomes greater than end

if not, print the subarray from index start to end and increment the starting index.

Code Solution

#include <iostream>
#include <vector>
using namespace std; 

void solution_1(vector<int> &arr)
{
    int n = arr.size();

    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            for (int k = i; k <= j; k++)
                cout << arr[k] << " ";
            cout << endl;
        }
    }
}

void solution_2(vector<int>& arr, int start, int end)
{

	//base case
    if (end == arr.size())
        return;

    else if (start > end)
        solution_2(arr, 0, end + 1);

    else {
        for (int i = start; i <= end; i++)  
            cout << arr[i] << " ";
        cout << endl;
        solution_2(arr, start + 1, end);  
    }
}

int main()
{
    vector<int> arr = {1, 2, 3, 4};
    
    cout << "Solution 1:\n";
    solution_1(arr);

    cout << "\nSolution 2:\n";
    solution_2(arr, 0, 0);    
    return 0;
}

Output

Solution 1:
1 
1 2 
1 2 3 
1 2 3 4 
2 
2 3 
2 3 4 
3 
3 4 
4 

Solution 2:
1 
1 2 
2 
1 2 3 
2 3 
3 
1 2 3 4 
2 3 4 
3 4 
4