Given an array, generate all the possible subarrays of the given array 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 have discussed iterative program to generate all subarrays. In this post, recursive is discussed.
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 <bits/stdc++.h>using namespace std;// Recursive function to print all possible subarrays for// given arrayvoid 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 start from 0 else if (start > end) printSubArrays(arr, 0, end + 1); // Print the subarray and increment the starting point else { cout << "["; for (int i = start; i < end; i++) cout << arr[i] << ", "; cout << arr[end] << "]" << endl; printSubArrays(arr, start + 1, end); } return;}int main(){ vector<int> arr = { 1, 2, 3 }; printSubArrays(arr, 0, 0); return 0;}// This code is contributed by Sania Kumari Gupta |
C
// C code to print all possible subarrays for given array// using recursion#include <stdio.h>// Recursive function to print all possible subarrays for// given arrayvoid 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]); // cout << arr[i] << ", "; printf("%d]\n", arr[end]); // cout << arr[end] << "]" << endl; 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;}// This code is contributed by Sania Kumari Gupta |
Java
// Java code to print all possible subarrays for given array// using recursionclass 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); }}// This code is contributed by Sania Kumari Gupta |
Python3
# Python3 code to print all possible subarrays# for given array using recursion# Recursive function to print all possible subarrays# for given arraydef 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 codearr = [1, 2, 3]printSubArrays(arr, 0, 0) |
C#
// C# code to print all possible subarrays// for given array using recursionusing 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); }}// This code is contributed by Rajput-Ji |
PHP
<?php// PHP code to print all possible// subarrays for given array using recursion// Recursive function to print all// possible subarrays for given arrayfunction printSubArrays($arr, $start, $end){ // Stop if we have reached // the end of the array if ($end == count($arr)) return; // Increment the end point // and start from 0 else if ($start > $end) return printSubArrays($arr, 0, $end + 1); // Print the subarray and increment // the starting point else { echo "["; for($i = $start; $i < $end + 1; $i++) { echo $arr[$i]; if($i != $end) echo ", "; } echo "]\n"; return printSubArrays($arr, $start + 1, $end); }}// Driver code$arr = array(1, 2, 3);printSubArrays($arr, 0, 0);// This code is contributed by mits?> |
Javascript
<script>// Javascript code to print all possible// subarrays for given array using recursion// Recursive function to print all// possible subarrays for given arrayfunction printSubArrays(arr, start, 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 { document.write("["); for(var i = start; i < end; i++) { document.write( arr[i] + ", "); } document.write(arr[end] + "]<br>"); printSubArrays(arr, start + 1, end); } return;}// Driver codevar arr = [ 1, 2, 3 ];printSubArrays(arr, 0, 0);// This code is contributed by rutvik_56</script> |
Output:
[1] [1, 2] [2] [1, 2, 3] [2, 3] [3]
Time Complexity: O(2n)
Auxiliary Space: O(2n)
