Generating subarrays using recursion

Examples :

 Input: [1, 2, 3] Output: [1], [1, 2], [2], [1, 2, 3 ], [2, 3], [3] Input: [1, 2] Output: [1], [1, 2], [2] 

We discussed an iterative program to generate all subarrays . This post discusses recursive.

Approach: we use two start and end pointers to maintain the start and end points of the array and follow the steps below:

  • Stop if we reach the end of the array
  • Increase the end index if start there is more end
  • Output a subarray from start to end index and increase starting index

Below is the implementation of the above approach.

C ++

// C ++ code to print all possible subarrays
// for a given array using recursion

 
# include & lt; iostream & gt;
# include & lt; vector & gt;

using namespace std;

 
// Recursive function to print all possible subarrays
// for this array

void printSubArrays (vector & lt; int & gt; arr, int start, int end)

// Stop if we have reached the end of the array

if (end == arr.size ()) 

return ;

 

// Increase the end point and start at 0

  else if (start & gt; end) 

  printSubArrays (arr, 0, end + 1);

 

// Display the subarray and increase the starting point

  else

{

  cout & lt; & lt; "[" ;

for ( int i = start; i & lt; end; i ++) {

cout & lt; & lt; arr [i] & lt; & lt; "," ;

}

 

  cout & lt; & lt; arr [end] & lt; & lt; "]" & lt; & lt; endl;

printSubArrays (arr, start + 1, end);

}

 

  return ;

}

 

int main ()

{

vector & lt; int & gt; arr = {1, 2, 3};

printSubArrays (arr, 0, 0);

return 0;

}

Java

// Java code for printing all possible subarrays
// for this array using recursion

 

class solution

{

  
// Recursive function to print all possible subarrays
// for this array

static void printSubArrays ( int [] arr, int start, int end)

// Stop if we reach the end of the array

  if (end == arr.length) 

return ;

 

// Increase the end point and start at 0

  else if (start & gt; end) 

printSubArrays (arr, 0 , end + 1 );

 

// Display the subarray and increase the starting point

  else

{

System.out.print ( "[" );

for ( int i = start; i & lt; end; i ++) {

System.out.print (arr [i] + ", " );

}

 

  System.out.println (arr [end] + "]" );

printSubArrays (arr, start + 1 , end);

}

 

  return ;

}

 

public static void main ( String args [])

{

int [] arr = { 1 , 2 , 3 };

printSubArrays (arr, 0 , 0 );

 
}
}

python3

# Python3 code to print all possible subarrays
# for a given array using recursion

 
# Recursive function to print all possible subarrays
# for a given array

def printSubArrays (arr, start, end):

 

# Stop if we have reached the end of the array

if end = = len (arr):

return

 

# Increase the endpoint and starting at 0

elif start & gt ; end:

return printSubArrays (arr , 0 , end + 1 )

  

# Print subarray and enlarge initial

# dot

else :

print (arr [start: end + 1 ])

return printSubArrays (arr, start + 1 , end)

 
# Driver code

arr = [ 1 , 2 , 3 ]

printSubArrays (arr, 0 , 0 )

C #

// C # code for printing all possible subarrays
// for this array using recursion

using System;

 

class GFG 

  

// Recursive function to print all

// possible subarrays for this array

  static void printSubArrays ( int [] arr, 

int start, int end) 

 

  / / Stop, e If we have reached

// end of array

if (end == arr.Length) 

return

 

// Increase the endpoint

  // and start at 0

else if (start & gt; end) 

  printSubArrays (arr, 0, end + 1 ); 

 

// Print the subarray and

  // increase the starting point

else

 

Console.Write ( "[" ); 

for ( int i = start; i & lt; end; i ++)

  Console.Write (arr [i] + "," ); 

 

  Console.WriteLine (arr [end] + "]" ); 

printSubArrays (arr, start + 1, end); 

return

 

  // Driver code

public static void Main (String [] args) 

int [] arr = { 1, 2, 3}; 

printSubArrays (arr, 0, 0); 

  
// This code is provided by Rajput-Ji

PHP

& lt ;? php
// PHP code to print everything possible
// subarrays for this array using recursion

 
// Recursive function to print all
// possible subarrays for this array

function printSubArrays ( $ arr , $ start , $ end )

// Stop if we reached

// end of array

if ( $ end == count ( $ arr ))

return ;

 

// Increase the endpoint

  // and start at 0

else if ( $ start & gt; $ end )

return printSubArrays ( $ arr , 0, 

$ end + 1);

 

// Print subarray and increment

  // starting point

else

  {

echo "[" ;

for ( $ i = $ start ; $ i & lt; $ end + 1; $ i ++)

{

echo $ arr [ $ i ];

if ( $ i ! = $ end )

echo "," ;

}

echo "] " ;

return printSubArrays ( $ arr , $ start + 1, 

$ end ) ;

}

  
// Driver code

$ arr = array (1, 2, 3);

printSubArrays ( $ arr , 0, 0);

 
// This code is provided by mits
? & gt;

Exit:

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

Complexity of time: