Generando subarreglos usando recursividad

Dada una array, genera todos los subarreglos posibles de la array dada usando la recursividad.

Ejemplos: 

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

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

Hemos discutido el programa iterativo para generar todos los subarreglos . En este post, se discute recursiva.

Enfoque: usamos dos punteros de inicio y final para mantener el punto inicial y final de la array y seguimos los pasos que se detallan a continuación: 

• Detener si hemos llegado al final de la array.
• Incremente el índice final si el inicio se ha vuelto mayor que el final
• Imprima el subarreglo desde el inicio del índice hasta el final e incremente el índice inicial

A continuación se muestra la implementación del enfoque anterior.  

// 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 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 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 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]);
       
        // 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 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);
    }
}
 
// This code is contributed by Sania Kumari Gupta

# 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);
    }
}
 
// This code is contributed by Rajput-Ji

<?php
// PHP 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)
{
    // 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
?>

<script>
 
// 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)
{
     
    // 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 code
var arr = [ 1, 2, 3 ];
printSubArrays(arr, 0, 0);
 
// This code is contributed by rutvik_56
 
</script>

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

Complejidad del tiempo:  O(2 ⁿ )

Espacio Auxiliar: O(2 ⁿ )