Day 55: Recursion Hard Mode | Subsequences & Power Set ⚡

📅 Date: Jan 18, 2026

🧠 Mood: Creating Multiverse 🌌

🔥 Topic: DSA: Subsequences (The Include/Exclude Pattern)

🤔 Subsequence vs Substring

First, clear this confusion.

• Substring: Continuous part. (e.g., for "ABC" -> "AB" is valid, "AC" is NOT).
• Subsequence: Order must be same, but can be discontinuous. (e.g., for "ABC" -> "AC" is valid).

Task: Find ALL subsequences of string "abc".
Output: "", "a", "b", "c", "ab", "ac", "bc", "abc"

---

⚡ The Magic Logic: Include or Exclude?

For every character in the string, we have exactly 2 Choices:

1. Take it (Include): Add it to our output string.
2. Leave it (Exclude): Ignore it and move to the next.

This creates a binary tree of possibilities.

---

💻 The C++ Code

This is a standard template used in many hard problems. Memorize the pattern!

#include <iostream>
#include <vector>
using namespace std;

void solve(string str, string output, int index, vector<string>& ans) {
    
    // 1. BASE CASE
    // When we finish processing the entire string
    if(index >= str.length()) {
        if(output.length() > 0) {
            ans.push_back(output);
        }
        return;
    }

    // 2. EXCLUDE (Nahi lena)
    solve(str, output, index+1, ans);

    // 3. INCLUDE (Lena hai)
    char element = str[index];
    output.push_back(element);
    solve(str, output, index+1, ans);
}

int main() {
    string str = "abc";
    string output = "";
    vector<string> ans;
    
    // Start Recursion from index 0
    solve(str, output, 0, ans);

    cout << "All Subsequences are: " << endl;
    for(string i : ans) {
        cout << "-> " << i << endl;
    }
    
    return 0;
}

🧠 Dry Run (Mental Model)

String: "ab"
Index 0 ('a'):
├── Exclude 'a' -> Output: ""
│ └── Index 1 ('b'):
│ ├── Exclude 'b' -> Final: "" (Empty Set)
│ └── Include 'b' -> Final: "b"
└── Include 'a' -> Output: "a"
└── Index 1 ('b'):
├── Exclude 'b' -> Final: "a"
└── Include 'b' -> Final: "ab"

---

🚀 Day 55 Challenge

1. Subsets of Array: Use the same logic to find subsets of `{1, 2, 3}`. The output should be vectors inside a vector.
2. Phone Keypad Problem: (LeetCode Medium)
   If I press '2', options are "a,b,c". If I press '3', options are "d,e,f".
   Print all combinations for "23". (Hint: It's just recursion!).

Next Up: Day 56 - Sorting Algorithms (Bubble, Selection, Insertion).