L6. Recursion on Subsequences | Printing Subsequences

1. Introduction and Problem Statement

When exploring recursion, one of the foundational patterns involves making multiple recursive calls to solve combinatorial problems. A classic domain for this pattern is generating and printing subsequences.

Before jumping into code, it is critical to distinguish between subsequences and subarrays:

• Subarray: A contiguous part of an array.
• Subsequence: A contiguous or non-contiguous sequence of elements that strictly follows the original order of elements in the array.

Real-Life Analogy: The Shopping Mall Trial Room

Analogy: Imagine you are in a shopping mall trial room trying on outfits. You have a rack of clothes (3, 1, 2). To try a specific combination, you put on an item (analogous to push_back or adding an element to your current data structure). To try an alternative outfit without that item, you must take off the current item before trying the next combination (analogous to pop_back or removing the element). If you never take off the clothes you tried, your next outfit will incorrectly pile on top of the old one.

2. Defining Subsequences with an Example

Consider an array of size $3$: arr = [3, 1, 2].

If we extract elements while maintaining their relative order, we get the following valid subsequences ($2^3 = 8$ total possibilities):

Invalid Subsequence Example: [3, 2, 1] is not a valid subsequence because the original order in [3, 1, 2] dictates that 1 must precede 2.

3. The Core Mental Model: Take and Not-Take

For every index in the array, we have a binary choice:

1. Take (Pick) the element at the current index into our temporary data structure and move to the next index.
2. Not-Take (Skip) the element at the current index and move to the next index without including it.

By branching into these two choices for every single element from index $0$ to $N-1$, we explore all $2^N$ possible subsets.

4. Step-by-Step Recursive Function Architecture

To implement this in code, we maintain:

• index: The current position we are deciding on.
• ds (Data Structure / Vector / List): The temporary container holding our current subsequence.
• arr: The original input array.
• n: The total size of the array.

Base Case

When index == n, we have exhausted all choices for all indices. At this point, our ds contains a fully formed valid subsequence. We print its contents and return.

5. Complete Implementation (C++)

Below is the robust C++ implementation demonstrating the Take, Backtrack (Remove), and Not-Take workflow:

#include <iostream>
#include <vector>

using namespace std;

void printSubsequences(int index, vector<int>& ds, int arr[], int n) {
    // Base Case: When we cross the last index, print the subsequence
    if (index == n) {
        if (ds.size() == 0) {
            cout << "{}" << endl; // Printing empty set representation
        } else {
            cout << "[ ";
            for (auto it : ds) {
                cout << it << " ";
            }
            cout << "]" << endl;
        }
        return;
    }

    // 1. TAKE / PICK choice
    ds.push_back(arr[index]);
    printSubsequences(index + 1, ds, arr, n);
    
    // BACKTRACK: Remove the element to undo the choice
    ds.pop_back();

    // 2. NOT-TAKE / SKIP choice
    printSubsequences(index + 1, ds, arr, n);
}

int main() {
    int arr[] = {3, 1, 2};
    int n = 3;
    vector<int> ds;
    
    printSubsequences(0, ds, arr, n);
    return 0;
}

6. Detailed Walkthrough of Trace and Backtracking

Let us trace what happens during execution for arr = [3, 1, 2] at the very beginning:

1. printSubsequences(0, [], arr, 3) is called.
2. Index is 0 (not equal to 3).
3. Take branch:
   • ds.push_back(arr[0]) -> ds becomes [3].
   • Recurse: printSubsequences(1, [3], arr, 3).
4. Inside index = 1:
   • Take branch: ds.push_back(arr[1]) -> ds becomes [3, 1].
   • Recurse: printSubsequences(2, [3, 1], arr, 3).
5. Inside index = 2:
   • Take branch: ds.push_back(arr[2]) -> ds becomes [3, 1, 2].
   • Recurse: printSubsequences(3, [3, 1, 2], arr, 3).
6. Inside index = 3:
   • Base case matches (index == n).
   • Prints [ 3 1 2 ] and returns.
7. Back at index = 2:
   • Backtrack step executes: ds.pop_back() removes 2. ds reverts from [3, 1, 2] back to [3, 1].
   • Not-Take branch: Recurse with printSubsequences(3, [3, 1], arr, 3).
8. Base case matches (index == n).
   • Prints [ 3 1 ] and returns.

This exact mechanics of pushing before the recursive call, and popping right after, ensures our state is clean and accurate for the alternate (Not-Take) branch.

7. Recursion Tree Visualization

The entire execution spawns a binary recursion tree of depth $N$. Here is how the structure branches for [3, 1, 2]:

                    f(0, [])
                   /        \
         (Pick 3) /          \ (Skip 3)
                 v            v
             f(1, [3])      f(1, [])
             /      \        /      \
      (Pick 1)      (Skip 1)(Pick 1) (Skip 1)
         v              v       v          v
     f(2,[3,1])     f(2,[3])  f(2,[1])   f(2, [])
      /      \       /    \    /    \     /     \
    f(3)    f(3)   f(3)  f(3) f(3)  f(3) f(3)   f(3)
   [3,1,2]  [3,1]  [3,2] [3]  [1,2] [1]  [2]    []
  (Printed)(Printed)(Printed)(Printed)(Printed)(Printed)(Printed)(Printed)

8. Complexity Analysis

Time Complexity

• Tree Branching: At every index, we make $2$ recursive choices (Take and Not-Take). For an array of size $N$, there are $2^N$ total subsequences.
• Printing Cost: Printing each subsequence takes proportional time to its length, bounded by $O(N)$.
• Total Time Complexity: $O(2^N \times N)$

Space Complexity

• Auxiliary Stack Space: The maximum depth of the recursive call stack is equal to the size of the array, $N$.
• Data Structure Space: The temporary list ds holds at most $N$ elements at any given time.
• Total Space Complexity: $O(N)$ (excluding the memory required to store output results).

9. Summary and Key Takeaways

• Definition: A subsequence maintains the original relative order of elements from an array and can be contiguous or non-contiguous.
• The Core Pattern: Every element presents a binary choice: Take it or Not-Take it.
• Total Subsequences: An array of size $N$ always yields exactly $2^N$ subsequences.
• The Role of Backtracking: When using a shared data structure (ds), you must pop/remove the element after the "Take" recursive call completes so that the subsequent "Not-Take" branch operates on a pristine state.
• Order of Execution: Swapping the order of the Take and Not-Take blocks alters the output order (e.g., printing empty sets or smaller prefixes first versus ending with them).
• Complexity Profile: Generates results in $O(2^N \times N)$ time while requiring only $O(N)$ auxiliary stack space.