Generating all possible Subsequences using Recursion

Software Development
#1

Hello Everyone,

Given an array. The task is to generate and print all of the possible subsequences of the given array using recursion.
Examples:

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]

Approach: For every element in the array, there are two choices, either to include it in the subsequence or not include it. Apply this for every element in the array starting from index 0 until we reach the last index. Print the subsequence once the last index is reached.

Below is the implementation of the above approach.

// C++ code to print all possible
// subsequences for given array using
// recursion
#include <bits/stdc++.h>
using namespace std;

void printArray(vector arr, int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

// Recursive function to print all
// possible subsequences for given array
void printSubsequences(vector arr, int index,
vector subarr)
{
// Print the subsequence when reach
// the leaf of recursion tree
if (index == arr.size())
{
int l = subarr.size();

    // Condition to avoid printing
    // empty subsequence
    if (l != 0)
        printArray(subarr, l);
}
else
{
    // Subsequence without including
    // the element at current index
    printSubsequences(arr, index + 1, subarr);

    subarr.push_back(arr[index]);

    // Subsequence including the element
    // at current index
    printSubsequences(arr, index + 1, subarr);
}
return;

}

// Driver Code
int main()
{
vector arr{1, 2, 3};
vector b;

printSubsequences(arr, 0, b);

return 0;

}

Output:

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

Time Complexity: O(2^n)

Note:

Recursion

Recursion means “defining a problem in terms of itself”. This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2)

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself.

For example, we can define the operation “find your way home” as:

  1. If you are at home, stop moving.
  2. Take one step toward home.
  3. “find your way home”.

Here the solution to finding your way home is two steps (three steps). First, we don’t go home if we are already home. Secondly, we do a very simple action that makes our situation simpler to solve. Finally, we redo the entire algorithm.

The above example is called tail recursion. This is where the very last statement is calling the recursive algorithm. Tail recursion can directly be translated into loops.

Parts of a Recursive Algorithm

All recursive algorithms must have the following:

  1. Base Case (i.e., when to stop)
  2. Work toward Base Case
  3. Recursive Call (i.e., call ourselves)

The “work toward base case” is where we make the problem simpler (e.g., divide list into two parts, each smaller than the original). The recursive call, is where we use the same algorithm to solve a simpler version of the problem. The base case is the solution to the “simplest” possible problem (For example, the base case in the problem ‘find the largest number in a list’ would be if the list had only one number… and by definition if there is only one number, it is the largest).