DSA Day 68: Combinatorics (Friends & Binary Strings)

📅 Date: June 19, 2026

🧠 Mood: The Combinator 🎲

🔥 Topic: DSA Day 68: Combinatorics (Friends & Binary Strings)

🎲 The Weekend Final Boss

It's Friday. The urge to shut the laptop, hit the gym in Thane, and start the weekend is incredibly high. But there are two topics left in "Recursion Part 2" that deal with generating combinations based on strict constraints.

The first is the Friends Pairing Problem: Given $N$ friends, each friend can either remain single or pair up with one other person. How many total ways can they be arranged? The second is generating all possible Binary Strings of size $N$ without any consecutive 1s. Both require building massive, branching recursive trees. I grabbed a pen, forced myself to dry-run the logic, and knocked them out.

---

🔗 Constraints and Choices

Let's look at the Binary String problem, because it visually demonstrates how a single constraint prunes a recursive tree. We need to generate strings of length $N$ using only '0' and '1', but '1' cannot sit next to another '1'.

Case 1: Previous char was '0'

If the last character we placed was a '0', we have total freedom. We can branch off and place a '0' for the next step, OR we can place a '1'. Both paths are valid.

Case 2: Previous char was '1'

If the last character was a '1', our choices are severely restricted by the rule. We CANNOT place another '1'. We are forced to place a '0'. The branch that would have placed a '1' is completely pruned from the tree.

---

💻 The C++ Implementation

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

// n = remaining length, lastPlace = the last character we added
void printBinStrings(int n, int lastPlace, string str) {
    // 1. BASE CASE
    if (n == 0) {
        cout << str << endl;
        return;
    }

    // 2. RECURSIVE CHOICES
    // We can ALWAYS append a '0'
    printBinStrings(n - 1, 0, str + "0");
    
    // We can ONLY append a '1' if the last place was NOT '1'
    if (lastPlace == 0) {
        printBinStrings(n - 1, 1, str + "1");
    }
}

int main() {
    int stringLength = 3;
    cout << "Valid binary strings of length " << stringLength << ":" << endl;
    
    // We pass 0 as the initial lastPlace to give the first choice maximum freedom
    printBinStrings(stringLength, 0, "");
    
    return 0;
}

---

🎯 Module Complete

The "Recursion Part 2" module is officially done. The syllabus lists a PDF of Assignment Questions next, which means my weekend is going to be spent struggling with blank screens and compiler errors. Time to log off and rest the brain.