L7: All Kinds of Patterns in Recursion | Print All | Print One | Count

This chapter explores fundamental recursion patterns revolving around subsequences, specifically tackling problems where we need to find subsequences whose elements add up to a given target sum ($K$). Building on the "take and not-take" paradigm from previous lessons, this guide examines three distinct structural variations: printing all valid subsequences, printing only one valid subsequence, and counting the total number of valid subsequences.

1. Why Do We Need These Recursion Patterns?

When solving combinatorial problems like finding subsequences that meet a specific condition (e.g., target sum), a naive brute-force approach quickly becomes inefficient without a structured template.

• In dynamic programming and advanced backtracking, the patterns taught here form the exact backbone of state exploration.
• Whether we need to display every valid path, short-circuit after finding a single solution, or tally up total possibilities, mastering these structural templates is essential for algorithmic problem-solving.

2. Core Mental Model: The Take and Not-Take Tree

To generate all subsequences of an array (such as [1, 2, 1] with sum K = 2), we traverse a binary recursion tree at every index. At each step, we have two primary choices:

1. Pick (Take): Include the current element in our temporary data structure (DS) and add its value to our running sum.
2. Not Pick (Not Take): Skip the current element, leaving our data structure and running sum unchanged.

Real-Life Analogy

Analogy: Think of choosing items from a buffet line where each dish has a fixed calorie count. As you walk down the line (index $0 \rightarrow 1 \rightarrow 2$), you make a binary choice at each dish: either put it on your plate (pick) or let it pass (not pick). At the end of the line, you check if the total calories on your plate match your exact dietary target ($K$).

3. Pattern 1: Printing All Subsequences Whose Sum Equals $K$

To print all valid subsequences, we must explore every branch of the recursion tree. We carry a temporary data structure (ds) and a running sum variable (s).

Step-by-Step Evolution & Code Implementation (C++)

When we reach the end of the array (index == n), we check if our accumulated sum equals the target sum $K$. If it does, we print the data structure.

#include <iostream>
#include <vector>

using namespace std;

void printS(int index, vector<int>& ds, int s, int sum, int arr[], int n) {
    // Base Case: Reached the end of the array
    if (index == n) {
        if (s == sum) {
            for (auto it : ds) cout << it << " ";
            cout << endl;
        }
        return;
    }

    // 1. Pick the current element
    ds.push_back(arr[index]);
    s += arr[index];
    printS(index + 1, ds, s, sum, arr, n);

    // Backtrack: Remove the element from DS and sum before "not pick"
    s -= arr[index];
    ds.pop_back();

    // 2. Not pick the current element
    printS(index + 1, ds, s, sum, arr, n);
}

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

4. Pattern 2: Printing Only ONE Subsequence Whose Sum Equals $K$

Often, problems do not require all possible answers—they ask for any single valid answer. Continuing to search the entire recursion tree after finding one valid subsequence is redundant and wastes computational time.

The Boolean Function Technique

To short-circuit and terminate recursion early once a valid answer is found:

1. Make the recursive function return a bool (true if a valid answer was found, false otherwise).
2. In the base case, if the condition is satisfied, return true. Otherwise, return false.
3. When making recursive calls, check if the call returns true. If it does, immediately return true to bubble up and halt further branch exploration.

Code Implementation (Printing Only One)

bool printSOne(int index, vector<int>& ds, int s, int sum, int arr[], int n) {
    // Base Case
    if (index == n) {
        if (s == sum) {
            for (auto it : ds) cout << it << " ";
            cout << endl;
            return true; // Found a valid subsequence!
        }
        return false; // Condition not met
    }

    // 1. Pick
    ds.push_back(arr[index]);
    s += arr[index];
    if (printSOne(index + 1, ds, s, sum, arr, n) == true) {
        return true; // Short-circuit: stop further exploration
    }

    // Backtrack
    s -= arr[index];
    ds.pop_back();

    // 2. Not Pick
    if (printSOne(index + 1, ds, s, sum, arr, n) == true) {
        return true; // Short-circuit: stop further exploration
    }

    return false; // Neither pick nor not pick yielded a valid sum here
}

5. Pattern 3: Counting the Total Number of Subsequences

When a problem asks for how many subsequences satisfy a condition rather than printing them, we eliminate the data structure entirely and focus on returning integer counts from our branches.

The Counting Rules

• Base Case (Condition Satisfied): Return 1 (we found one valid path).
• Base Case (Condition Not Satisfied): Return 0 (this path is invalid).
• Recursive Combination: Compute results from the left (pick) and right (not pick) recursive calls, then return their sum (left + r).

Code Implementation (Counting)

int countSubsequences(int index, int s, int sum, int arr[], int n) {
    // Condition satisfied base case
    if (index == n) {
        if (s == sum) return 1;
        return 0;
    }

    // 1. Pick current element
    s += arr[index];
    int left = countSubsequences(index + 1, s, sum, arr, n);

    // Backtrack sum
    s -= arr[index];

    // 2. Not pick current element
    int right = countSubsequences(index + 1, s, sum, arr, n);

    // Return total valid paths from both choices
    return left + right;
}

6. Structural Pattern Summary Table

7. Complexity Analysis & Optimization Mindset

Time & Space Complexity

• Time Complexity: $\mathcal{O}(2^n)$, because at every index we branch into 2 choices (pick vs. not pick), resulting in a binary recursion tree of depth $n$.
• Space Complexity: $\mathcal{O}(n)$ auxiliary stack space used by the recursion call stack (plus space for the temporary data structure if printing).

Early Exit Optimization (Positive Arrays Only)

If the input array contains strictly positive numbers, we can optimize our search space:

// Optimization inside recursive function:
if (s > sum) return; // If running sum exceeds target, further picks will only increase it!

Note: This optimization (s > sum) only works safely if all array elements are positive integers. If negative numbers or zeros are present, adding an element could decrease or keep the sum unchanged, invalidating this shortcut.

8. Summary and Key Takeaways

• The Take/Not-Take Framework: Forms the bedrock of subset and subsequence generation algorithms in recursion and dynamic programming.
• State Management: Always maintain your running variables (index, ds, sum) carefully across recursive boundaries and backtrack (undo changes) when returning from a pick call.
• Printing All: Uses a void return type, traversing every single leaf node in the recursion tree.
• Printing One: Uses a bool return type with an early if check to short-circuit and terminate unnecessary recursion once a valid path is found.
• Counting: Uses an int return type, returning 1 or 0 at base cases and summing up branch results (left + right).
• Time Complexity Reality: Expect exponential time complexity $\mathcal{O}(2^n)$ for subset generation problems unless pruned by specific problem constraints.