Generando todas las Subsecuencias posibles usando Recursión incluyendo la vacía.

Dada una array. La tarea es generar e imprimir todas las subsecuencias posibles de la array dada usando recursividad.

Ejemplos: 

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

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

Enfoque: para cada elemento de la array, hay dos opciones, incluirlo en la subsecuencia o no incluirlo. Aplique esto para cada elemento de la array a partir del índice 0 hasta llegar al último índice. Imprime la subsecuencia una vez que se alcanza el último índice. 

El siguiente diagrama muestra el árbol de recurrencia para la array, arr[] = {1, 2} .  

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

// C++ code to print all possible
// subsequences for given array using
// recursion
#include <bits/stdc++.h>
using namespace std;
 
 
 
// Recursive function to print all
// possible subsequences for given array
void printSubsequences(int arr[], int index,
                       vector<int> &subarr,int n)
{
    // Print the subsequence when reach
    // the leaf of recursion tree
    if (index == n)
    {
         for (auto it:subarr){
           cout << it << " ";
          
         }
      if(subarr.size()==0)
        cout<<"{}";
       
      cout<<endl;
      return;
 
         
    }
    else
    {
       //pick the current index into the subsequence.
        subarr.push_back(arr[index]);
       
 
         printSubsequences(arr, index + 1, subarr,n);
 
         
        subarr.pop_back();
       
      //not picking the element into the subsequence.
        printSubsequences(arr, index + 1, subarr,n);
    }
    
}
 
// Driver Code
int main()
{
    int arr[]={1, 2, 3};
    int n=sizeof(arr)/sizeof(arr[0]);
    vector<int> vec;
      
 
    printSubsequences(arr, 0, vec,n);
 
    return 0;
}
 
// This code is contributed by
// vivekr4400

// Java code to print all possible
// subsequences for given array using
// recursion
import java.io.*;
import java.util.*;
 
class GFG{
       
// Recursive function to print all
// possible subsequences for given array
public static void printSubsequences(int[] arr, int index,
                                     ArrayList<Integer> path)
{
     
    // Print the subsequence when reach
    // the leaf of recursion tree
    if (index == arr.length)
    {
         
        // Condition to avoid printing
        // empty subsequence
        if (path.size() > 0)
            System.out.println(path);
    }
     
    else
    {
         
        // Subsequence without including
        // the element at current index
        printSubsequences(arr, index + 1, path);
         
        path.add(arr[index]);
         
        // Subsequence including the element
        // at current index
        printSubsequences(arr, index + 1, path);
         
        // Backtrack to remove the recently
        // inserted element
        path.remove(path.size() - 1);
    }
    return;
}
 
// Driver code
public static void main(String[] args)
{
    int[] arr = { 1, 2, 3 };
       
      // Auxiliary space to store each path
      ArrayList<Integer> path = new ArrayList<>();
       
      printSubsequences(arr, 0, path);
}
}
 
// This code is contributed by Mukul Sharma

# Python3 code to print all possible 
# subsequences for given array using 
# recursion
   
# Recursive function to print all
# possible subsequences for given array
def printSubsequences(arr, index, subarr):
       
    # Print the subsequence when reach 
    # the leaf of recursion tree
    if index == len(arr):
           
        # Condition to avoid printing
        # empty subsequence
        if len(subarr) != 0:
            print(subarr)
       
    else:
        # Subsequence without including 
        # the element at current index
        printSubsequences(arr, index + 1, subarr)
           
        # Subsequence including the element
        # at current index
        printSubsequences(arr, index + 1, 
                            subarr+[arr[index]])
       
    return
           
arr = [1, 2, 3]
   
printSubsequences(arr, 0, [])
 
#This code is contributed by Mayank Tyagi

// C# code to print all possible
// subsequences for given array using
// recursion
using System;
using System.Collections.Generic;
class GFG {
     
    // Recursive function to print all
    // possible subsequences for given array
    static void printSubsequences(int[] arr, int index, List<int> path)
    {
          
        // Print the subsequence when reach
        // the leaf of recursion tree
        if (index == arr.Length)
        {
              
            // Condition to avoid printing
            // empty subsequence
            if (path.Count > 0)
            {
                Console.Write("[");
                for(int i = 0; i < path.Count - 1; i++)
                {
                    Console.Write(path[i] + ", ");
                }
                Console.WriteLine(path[path.Count - 1] + "]");
            }
        }
          
        else
        {
              
            // Subsequence without including
            // the element at current index
            printSubsequences(arr, index + 1, path);
              
            path.Add(arr[index]);
              
            // Subsequence including the element
            // at current index
            printSubsequences(arr, index + 1, path);
              
            // Backtrack to remove the recently
            // inserted element
            path.RemoveAt(path.Count - 1);
        }
        return;
    }
 
  static void Main() {
      int[] arr = { 1, 2, 3 };
        
      // Auxiliary space to store each path
      List<int> path = new List<int>();
        
      printSubsequences(arr, 0, path);
  }
}
 
// This code is contributed by rameshtravel07.

<script>
// Javascript code to print all possible
// subsequences for given array using
// recursion
 
// Recursive function to print all
// possible subsequences for given array
function printSubsequences(arr, index, path)
{
 
  // Print the subsequence when reach
  // the leaf of recursion tree
  if (index == arr.length)
  {
   
    // Condition to avoid printing
    // empty subsequence
    if (path.length > 0) document.write(`[${path}]<br>`);
  }
  else
  {
   
    // Subsequence without including
    // the element at current index
    printSubsequences(arr, index + 1, path);
 
    path.push(arr[index]);
 
    // Subsequence including the element
    // at current index
    printSubsequences(arr, index + 1, path);
 
    // Backtrack to remove the recently
    // inserted element
    path.pop();
  }
  return;
}
 
// Driver code
let arr = [1, 2, 3];
 
// Auxiliary space to store each path
let path = new Array();
 
printSubsequences(arr, 0, path);
 
// This code is contributed by gfgking
</script>

producción

1 2 3  

1 2  

1 3  

1  

2 3  

2  

3  

{}

Complejidad del tiempo: 

Complejidad espacial: 
O(n), debido a la pila de recursividad.