Generating All Subarrays

Last Updated : 07 Feb, 2025

Given an array arr[], the task is to generate all the possible subarrays of the given array.

Examples:

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

Input: arr[] = [1, 2]
Output: [ [1], [1, 2], [2] ]

Iterative Approach

To generate a subarray, we need a starting index from the original array. For choosing the starting index, we can run a loop from [0 to n-1] and consider each i as the starting index. For each starting index i, we can select an ending index from the range [i to n-1]. A nested loop from [i to n-1] will help in selecting the ending index. Once we have the starting and ending indices, we need an innermost loop to print the elements in this subarray.

Outermost Loop: Picks starting index of current subarray
Middle Loop: Picks ending index of current subarray
Innermost Loop: Prints the subarray from the starting index to the ending index

C++

#include <iostream> #include <vector> using namespace std; // Prints all subarrays in arr[0..n-1] void subArray(vector<int> &arr) {  int n = arr.size();  // Pick starting point  for (int i = 0; i < n; i++)  {  // Pick ending poin  for (int j = i; j < n; j++)  {  // Print subarray between current starting  // and ending points  for (int k = i; k <= j; k++)  cout << arr[k] << " ";  cout << endl;  }  } } int main() {  vector<int> arr = {1, 2, 3, 4};  cout << "All Non-empty Subarrays\n";  subArray(arr);  return 0; }

#include <stdio.h> //Prints all subarrays in arr[0..n-1] void subArray(int arr[], int n) {    // Pick starting point  for (int i = 0; i < n; i++) {    // Pick ending point  for (int j = i; j < n; j++) {    // Print subarray between current starting and ending points  for (int k = i; k <= j; k++) {  printf("%d ", arr[k]);  }  printf("\n");  }  } } int main() {  int arr[] = {1, 2, 3, 4};  int n = sizeof(arr) / sizeof(arr[0]);  printf("All Non-empty Subarrays:\n");  subArray(arr, n);  return 0; }

Java

import java.util.ArrayList; public class GfG {    //Prints all subarrays in arr[0..n-1]  static void subArray(ArrayList<Integer> arr) {  int n = arr.size();  // Pick starting point  for (int i = 0; i < n; i++) {    // Pick ending point  for (int j = i; j < n; j++) {    // Print subarray between current starting and ending points  for (int k = i; k <= j; k++) {  System.out.print(arr.get(k) + " ");  }  System.out.println();  }  }  }  public static void main(String[] args) {  ArrayList<Integer> arr = new ArrayList<>();  arr.add(1);  arr.add(2);  arr.add(3);  arr.add(4);  System.out.println("All Non-empty Subarrays:");  subArray(arr);  } }

Python

#Prints all subarrays in arr[0..n-1] def sub_array(arr): n = len(arr) # Pick starting point for i in range(n): # Pick ending point for j in range(i, n): # Print subarray between current starting and ending points for k in range(i, j + 1): print(arr[k], end=" ") print() # New line after each subarray # Driver code arr = [1, 2, 3, 4] print("All Non-empty Subarrays:") sub_array(arr)

using System; using System.Collections.Generic; class GfG {    //Prints all subarrays in arr[0..n-1]  static void SubArray(List<int> arr) {  int n = arr.Count;  // Pick starting point  for (int i = 0; i < n; i++) {    // Pick ending point  for (int j = i; j < n; j++) {    // Print subarray between current starting and ending points  for (int k = i; k <= j; k++) {  Console.Write(arr[k] + " ");  }  Console.WriteLine();  }  }  }  static void Main() {  List<int> arr = new List<int> { 1, 2, 3, 4 };  Console.WriteLine("All Non-empty Subarrays:");  SubArray(arr);  } }

JavaScript

//Prints all subarrays in arr[0..n-1] function subArray(arr) {  const n = arr.length;  // Pick starting point  for (let i = 0; i < n; i++) {    // Pick ending point  for (let j = i; j < n; j++) {    // Print subarray between current starting and ending points  let subarr = [];  for (let k = i; k <= j; k++) {  subarr.push(arr[k]);  }  console.log(subarr.join(" "));  }  } } const arr = [1, 2, 3, 4]; console.log("All Non-empty Subarrays:"); subArray(arr);

Output

All Non-empty Subarrays 1 1 2 1 2 3 1 2 3 4 2 2 3 2 3 4 3 3 4 4

Recursive Approach

We use two pointers start and end to maintain the starting and ending point of the array and follow the steps given below:

Stop if we have reached the end of the array
Increment the end index if start has become greater than end
Print the subarray from index start to end and increment the starting index

Below is the implementation of the above approach.

C++

// C++ code to print all possible subarrays for given array // using recursion #include <iostream> #include <vector> using namespace std; // Recursive function to print all possible subarrays for given array void printSubArrays(vector<int>& arr, int start, int end) {  // Stop if we have reached the end of the array  if (end == arr.size())  return;  // Increment the end point and reset the start to 0  else if (start > end)  printSubArrays(arr, 0, end + 1);  // Print the subarray and increment the starting point  else {  for (int i = start; i <= end; i++)   cout << arr[i] << " ";  cout << endl;  printSubArrays(arr, start + 1, end);   } } int main() {  vector<int> arr = {1, 2, 3};  printSubArrays(arr, 0, 0);  return 0; }

// C code to print all possible subarrays for given array // using recursion #include <stdio.h> // Recursive function to print all possible subarrays for // given array void printSubArrays(int arr[], int start, int end, int size) {    // Stop if we have reached the end of the array  if (end == size)  return;    // Increment the end point and start from 0  else if (start > end)  printSubArrays(arr, 0, end + 1, size);    // Print the subarray and increment the starting point  else {  printf("[");  for (int i = start; i < end; i++)  printf("%d, ", arr[i]);  printf("%d]\n", arr[end]);  printSubArrays(arr, start + 1, end, size);  }  return; } int main() {  int arr[] = { 1, 2, 3 };  int n = sizeof(arr) / sizeof(arr[0]);  printSubArrays(arr, 0, 0, n);  return 0; }

Java

// Java code to print all possible subarrays for given array // using recursion class solution {  // Recursive function to print all possible subarrays  // for given array  static void printSubArrays(int[] arr, int start, int end)  {   // Stop if we have reached the end of the array  if (end == arr.length)  return;  // Increment the end point and start from 0  else if (start > end)  printSubArrays(arr, 0, end + 1);  // Print the subarray and increment the starting  // point  else {  System.out.print("[");  for (int i = start; i < 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);  } }

Python

# Python3 code to print all possible subarrays  # for given array using recursion # Recursive function to print all possible subarrays  # for given array def printSubArrays(arr, start, end): # Stop if we have reached the end of the array  if end == len(arr): return # Increment the end point and start from 0 elif start > end: return printSubArrays(arr, 0, end + 1) # Print the subarray and increment the starting # point else: print(arr[start:end + 1]) return printSubArrays(arr, start + 1, end) # Driver code arr = [1, 2, 3] printSubArrays(arr, 0, 0)

// C# code to print all possible subarrays  // for given array using recursion  using System; class GFG  {   // Recursive function to print all   // possible subarrays for given array   static void printSubArrays(int []arr,   int start, int end)   {   // Stop if we have reached   // the end of the array   if (end == arr.Length)   return;   // Increment the end point   // and start from 0   else if (start > end)   printSubArrays(arr, 0, end + 1);   // Print the subarray and   // increment the starting point   else  {   Console.Write("[");   for (int i = start; i < 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);   }  }

JavaScript

// JavaScript code to print all possible  // subarrays for given array using recursion  // Recursive function to print all  // possible subarrays for given array  function printSubArrays(arr, start, end) {   if (end == arr.length)   return;    // Increment the end point and start  // from 0   else if (start > end)   printSubArrays(arr, 0, end + 1);    // Print the subarray and increment   // the starting point   else {  let subArray = "[";  for (var i = start; i < end; i++) {  subArray += arr[i] + ", ";  }  subArray += arr[end] + "]";  console.log(subArray);  printSubArrays(arr, start + 1, end);  }  return; } var arr = [1, 2, 3]; printSubArrays(arr, 0, 0);