How to Print Subsequences of an Array using recursion? 🤨

As we all know that Recursion is calling the function itself again and again until the base condition is satisfied. So,in order to make a recursive function we should keep in mind the base condition and the function definition we want to create.

Please note that ,here I will be writing the pseudo code . You can just implement the code in the language you are comfortable with .

So lets just not waste any second further and dive in !

At first we need to know what is a Subsequence and Subarray.

Consider an example ,a character array containing the word "hashnode" ( char arr[]={'h' , 'a' , 's' , 'h' , 'n' , 'o' , 'd' , 'e' } ).

Here "hash" is a subsequence and subarray as it is both contiguous and maintains relative ordering of elements in it.

A more vital example would be "hhne". Note that this word is not contiguous (i.e, there exists some alphabets which are skipped over) but it still maintains the relative order.

Lets move to the definitions:

Subsequence: It maintains relative ordering of elements, but may or may not be a contiguous part of the array(or string).

For a 'n' size array there exists 2^(n) subsequences including an empty array. For [1,2,3] the subsequences are [1] , [2] , [3] , [1,2] , [2,3] , [1,3] , [1,2,3] , [].

Subarray: It is a continguous part of an array preserving the relative ordering of the elements.

For a 'm' size array there exists m*(m+1)/2 subarrays. For example [2,8,5], the subarrays are [2] , [8] , [5] , [2,8] , [8,5] , [2,8,5] .

Notice that all subsequnces are not subarrays but all subarrays are subsequences.

I hope you got the idea :p

So how to find the subsequences now?🤔

Lets tackle the problem. First of all in order to print all the subsequnces we need to iterate through the whole array. So our base condition will be like :

if(n==size)
{
    print(array);
    return ;
}

here n is the size of the variable subsequnces we are going to print.

Overall our function will look like:

function print_Subsequence(index,size,arr[],vector<int>&vec)
{
  // Initially we will set the index as 0 for traversal of the whole array
  // arr is the array given to us and vec is the subsequence vector we will
  // be returning via recursion

   // base condition to be placed at very first position in the function
      if(index==size)
    {
       print(array) // print the whole array by iterating through for loop
       return; 
    }        
    // add the first element of the arr
    vec.add(arr[index])
    print_Subsequence(index+1,size,arr,vec)
    vec.remove() // remove the last element added to the vec 
    print_Subsequence(index+1,size,arr,vec) //continue the recursion 
}

The basic analogy behind this method is to add an element and then remove the same element while continuing the recusion until the base condition is satisfied.

If there's any typo or code error feel free to point out my mistake :).