Posted on by Kalkicode
Code Mathematics

# Generating all subarrays of an array

In the realm of computer science and programming, understanding arrays and their subarrays is a fundamental concept. Subarrays are contiguous portions of an array that can be analyzed individually. The task of generating all possible subarrays of an array is not only an important programming exercise but also finds applications in various algorithmic problems.

## Problem Statement

Given an array, the problem entails generating and printing all possible subarrays of the given array. A subarray is defined by two indices, the starting index (inclusive) and the ending index (exclusive), within the original array. The goal is to systematically extract and print all subarrays of varying lengths, beginning from each index of the array.

## Example and Description

Let's illustrate the problem with a simple example. Consider the array [1, 2, 3, 6]. The task is to generate all subarrays and print their elements.

## Step 1

• Subarray: [1]
• Subarray: [1, 2]
• Subarray: [1, 2, 3]
• Subarray: [1, 2, 3, 6]

## Step 2

Move to index 1. Generate subarrays starting from index 1:

• Subarray: [2]
• Subarray: [2, 3]
• Subarray: [2, 3, 6]

## Step 3

Move to index 2. Generate subarrays starting from index 2:

• Subarray: [3]
• Subarray: [3, 6]

## Step 4

Move to index 3. Generate subarrays starting from index 3:

• Subarray: [6]

Combine all the generated subarrays to get the complete list of subarrays: [1], [1, 2], [1, 2, 3], [1, 2, 3, 6], [2], [2, 3], [2, 3, 6], [3], [3, 6], [6].

## Idea to Solve

The problem can be solved by using two nested loops. The outer loop iterates through each index of the array, and the inner loop generates subarrays starting from the current index to the end of the array. A separate function can be defined to print the elements of a given subarray.

## Standard Pseudocode

function printSubarray(arr, start, last)
for i = start to last - 1
print arr[i]
end for
end function

function findSubArray(arr, n)
for i = 0 to n - 1
for j = i + 1 to n
printSubarray(arr, i, j)
end for
end for
end function

main
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
n = size of arr1
findSubArray(arr1, n)
n = size of arr2
findSubArray(arr2, n)
end main

## Algorithm Explanation

1. Define the printSubarray function that takes an array arr, a starting index start, and an ending index last as parameters. This function prints the elements of the subarray from index start to last - 1.
2. Define the findSubArray function that takes an array arr and its length n as parameters. This function generates and prints all subarrays of the given array.
• The outer loop iterates through each index i from 0 to n - 1.
• The inner loop iterates through each index j from i + 1 to n.
• Within the inner loop, the printSubarray function is called to print the subarray from index i to j - 1.
3. In the main function, define the arrays arr1 and arr2 with their respective elements.
4. Calculate the size of the arrays using the sizeof operator and the size of an individual element.
5. Call the findSubArray function for both arr1 and arr2.

## Code Solution

// C Program
// Generating all subarrays of an array
#include <stdio.h>

// Print resultant subarray
void printSubarray(int arr[], int start, int last)
{
for (int i = start; i < last; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
void findSubArray(int arr[], int n)
{
// Execute this loop through by array length
for (int i = 0; i < n; ++i)
{
// Inner loop from i+1 to n
for (int j = i + 1; j <= n; ++j)
{
// Print subarray in range [i..j]
printSubarray(arr, i, j);
}
}
}
int main(int argc, char const *argv[])
{
int arr1[] = {
1 , 2 , 3 , 6
};
int arr2[] = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = sizeof(arr1) / sizeof(arr1[0]);
findSubArray(arr1, n);
printf("\n");
// Test Case B
n = sizeof(arr2) / sizeof(arr2[0]);
findSubArray(arr2, n);
return 0;
}

#### input

1
1  2
1  2  3
1  2  3  6
2
2  3
2  3  6
3
3  6
6

7
7  8
7  8  1
7  8  1  6
7  8  1  6  4
8
8  1
8  1  6
8  1  6  4
1
1  6
1  6  4
6
6  4
4
// Java program for
// Generating all subarrays of an array
import java.util.ArrayList;
public class Subarrays
{
// Print resultant subarray
public void printSubarray(int[] arr, int start, int last)
{
for (int i = start; i < last; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
public void findSubArray(int[] arr, int n)
{
// Execute this loop through by array length
for (int i = 0; i < n; ++i)
{
// Inner loop from i+1 to n
for (int j = i + 1; j <= n; ++j)
{
// Print subarray in range [i..j]
printSubarray(arr, i, j);
}
}
}
public static void main(String[] args)
{
int[] arr1 = {
1 , 2 , 3 , 6
};
int[] arr2 = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = arr1.length;
System.out.print("\n");
// Test Case B
n = arr2.length;
}
}

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
#include <iostream>
using namespace std;

class Subarrays
{
public:
// Print resultant subarray
void printSubarray(int arr[], int start, int last)
{
for (int i = start; i < last; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
void findSubArray(int arr[], int n)
{
// Execute this loop through by array length
for (int i = 0; i < n; ++i)
{
// Inner loop from i+1 to n
for (int j = i + 1; j <= n; ++j)
{
// Print subarray in range [i..j]
this->printSubarray(arr, i, j);
}
}
}
};
int main()
{
int arr1[] = {
1 , 2 , 3 , 6
};
int arr2[] = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = sizeof(arr1) / sizeof(arr1[0]);
cout << "\n";
// Test Case B
n = sizeof(arr2) / sizeof(arr2[0]);
return 0;
}

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
// Include namespace system
using System;
public class Subarrays
{
// Print resultant subarray
public void printSubarray(int[] arr, int start, int last)
{
for (int i = start; i < last; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public void findSubArray(int[] arr, int n)
{
// Execute this loop through by array length
for (int i = 0; i < n; ++i)
{
// Inner loop from i+1 to n
for (int j = i + 1; j <= n; ++j)
{
// Print subarray in range [i..j]
this.printSubarray(arr, i, j);
}
}
}
public static void Main(String[] args)
{
int[] arr1 = {
1 , 2 , 3 , 6
};
int[] arr2 = {
7 , 8 , 1 , 6 , 4
};
// Test Case A
int n = arr1.Length;
Console.Write("\n");
// Test Case B
n = arr2.Length;
}
}

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
<?php
class Subarrays
{
// Print resultant subarray
public	function printSubarray(\$arr, \$start, \$last)
{
for (\$i = \$start; \$i < \$last; ++\$i)
{
echo(" ".\$arr[\$i]);
}
echo("\n");
}
public	function findSubArray(\$arr, \$n)
{
// Execute this loop through by array length
for (\$i = 0; \$i < \$n; ++\$i)
{
// Inner loop from i+1 to n
for (\$j = \$i + 1; \$j <= \$n; ++\$j)
{
// Print subarray in range [i..j]
\$this->printSubarray(\$arr, \$i, \$j);
}
}
}
}

function main()
{
\$arr1 = array(1, 2, 3, 6);
\$arr2 = array(7, 8, 1, 6, 4);
// Test Case A
\$n = count(\$arr1);
echo("\n");
// Test Case B
\$n = count(\$arr2);
}
main();

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
class Subarrays
{
// Print resultant subarray
printSubarray(arr, start, last)
{
for (var i = start; i < last; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
findSubArray(arr, n)
{
// Execute this loop through by array length
for (var i = 0; i < n; ++i)
{
// Inner loop from i+1 to n
for (var j = i + 1; j <= n; ++j)
{
// Print subarray in range [i..j]
this.printSubarray(arr, i, j);
}
}
}
}

function main()
{
var arr1 = [1, 2, 3, 6];
var arr2 = [7, 8, 1, 6, 4];
// Test Case A
var n = arr1.length;
process.stdout.write("\n");
// Test Case B
n = arr2.length;
}
main();

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
class Subarrays :
#  Print resultant subarray
def printSubarray(self, arr, start, last) :
i = start
while (i < last) :
print(" ", arr[i], end = "")
i += 1

print(end = "\n")

def findSubArray(self, arr, n) :
#  Execute this loop through by list length
i = 0
while (i < n) :
#  Inner loop from i+1 to n
j = i + 1
while (j <= n) :
#  Print sublist in range [i..j]
self.printSubarray(arr, i, j)
j += 1

i += 1

def main() :
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
#  Test Case A
n = len(arr1)
print(end = "\n")
#  Test Case B
n = len(arr2)

if __name__ == "__main__": main()

#### input

1
1  2
1  2  3
1  2  3  6
2
2  3
2  3  6
3
3  6
6

7
7  8
7  8  1
7  8  1  6
7  8  1  6  4
8
8  1
8  1  6
8  1  6  4
1
1  6
1  6  4
6
6  4
4
class Subarrays
#  Print resultant subarray
def printSubarray(arr, start, last)
i = start
while (i < last)
print(" ", arr[i])
i += 1
end

print("\n")
end

def findSubArray(arr, n)
i = 0
#  Execute this loop through by array length
while (i < n)

j = i + 1
#  Inner loop from i+1 to n
while (j <= n)
#  Print subarray in range [i..j]
self.printSubarray(arr, i, j)
j += 1
end

i += 1
end

end

end

def main()
arr1 = [1, 2, 3, 6]
arr2 = [7, 8, 1, 6, 4]
#  Test Case A
n = arr1.length
print("\n")
#  Test Case B
n = arr2.length
end

main()

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
class Subarrays()
{
// Print resultant subarray
def printSubarray(arr: Array[Int], start: Int, last: Int): Unit = {
var i: Int = start;
while (i < last)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
def findSubArray(arr: Array[Int], n: Int): Unit = {

var i: Int = 0;
// Execute this loop through by array length
while (i < n)
{

var j: Int = i + 1;
// Inner loop from i+1 to n
while (j <= n)
{
// Print subarray in range [i..j]
printSubarray(arr, i, j);
j += 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarrays = new Subarrays();
var arr1: Array[Int] = Array(1, 2, 3, 6);
var arr2: Array[Int] = Array(7, 8, 1, 6, 4);
// Test Case A
var n: Int = arr1.length;
print("\n");
// Test Case B
n = arr2.length;
}
}

#### input

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4
import Foundation;
class Subarrays
{
// Print resultant subarray
func printSubarray(_ arr: [Int], _ start: Int, _ last: Int)
{
var i = start;
while (i < last)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func findSubArray(_ arr: [Int], _ n: Int)
{
// Execute this loop through by array length
var i = 0;
while (i < n)
{
// Inner loop from i+1 to n
var j = i + 1;
while (j <= n)
{
// Print subarray in range [i..j]
self.printSubarray(arr, i, j);
j += 1;
}
i += 1;
}
}
}
func main()
{
let arr1 = [1, 2, 3, 6];
let arr2 = [7, 8, 1, 6, 4];
// Test Case A
var n = arr1.count;
print(terminator: "\n");
// Test Case B
n = arr2.count;
}
main();

#### input

1
1  2
1  2  3
1  2  3  6
2
2  3
2  3  6
3
3  6
6

7
7  8
7  8  1
7  8  1  6
7  8  1  6  4
8
8  1
8  1  6
8  1  6  4
1
1  6
1  6  4
6
6  4
4
class Subarrays
{
// Print resultant subarray
fun printSubarray(arr: Array < Int > , start: Int, last: Int): Unit
{
var i: Int = start;
while (i < last)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
fun findSubArray(arr: Array < Int > , n: Int): Unit
{

var i: Int = 0;
// Execute this loop through by array length
while (i < n)
{

var j: Int = i + 1;
// Inner loop from i+1 to n
while (j <= n)
{
// Print subarray in range [i..j]
this.printSubarray(arr, i, j);
j += 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val arr1: Array < Int > = arrayOf(1, 2, 3, 6);
val arr2: Array < Int > = arrayOf(7, 8, 1, 6, 4);
// Test Case A
var n: Int = arr1.count();
print("\n");
// Test Case B
n = arr2.count();
}

1
1 2
1 2 3
1 2 3 6
2
2 3
2 3 6
3
3 6
6

7
7 8
7 8 1
7 8 1 6
7 8 1 6 4
8
8 1
8 1 6
8 1 6 4
1
1 6
1 6 4
6
6 4
4

## Time Complexity

The time complexity of the solution is O(n^3), where 'n' is the length of the input array. This is because the two nested loops run in O(n^2) time, and within the innermost loop, the printSubarray function takes O(n) time in the worst case (printing a subarray of length 'n').

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post