Problem Statement

Given an integer n, print all n-bit binary numbers that have more 1's than 0's in any prefix of the binary number. Each number should have exactly n bits.

Examples

Example 1:

Input: n = 2
Output: "11"

Explanation:
Only "11" meets the condition. "10" and "01" would have equal numbers of 1's and 0's at some point in their prefixes.

Example 2:

Input: n = 3
Output: "111",
        "110"

Explanation: Both "111" and "110" meet the condition. "101" and "100" do not have more 1's than 0's in all prefixes.

Example 3:

Input n = 4
Output: "1111",
        "1110",
        "1101"
        
Explanation: The valid sequences are "1111", "1110", and "1101".
"1011" does not satisfy the requirement of having more 1's than 0's in every prefix.
    Prefix 1: "1"
        1s = 1, 0s = 0 valid (1 > 0)
    Prefix 10: "10"
        1s = 1, 0s = 0 = 1 Invalid (1 = 1, not more 1s
        than 0s)

Different Approaches

1️⃣ Recursion

Code:

#include <iostream>
#include <vector>
#include <string>

// Helper function to recursively generate valid binary numbers
void generateBinary(int n, int count1, int count0, std::string current, std::vector<std::string> &result) {
    // Base case: if the length of current string is n, add it to result
    if (current.length() == n) {
        result.push_back(current);
        return;
    }
    
    // Add '1' to the current string and recurse
    generateBinary(n, count1 + 1, count0, current + "1", result);

    // Add '0' to the current string only if there are more '1's than '0's so far
    if (count1 > count0) {
        generateBinary(n, count1, count0 + 1, current + "0", result);
    }
}

// Function to generate all valid n-bit binary numbers with more 1s than 0s in every prefix
std::vector<std::string> generateNBitBinary(int n) {
    std::vector<std::string> result;
    generateBinary(n, 0, 0, "", result);
    return result;
}

int main() {
    int n = 3;  // Change this to test different values of n
    std::vector<std::string> validBinaryStrings = generateNBitBinary(n);
    
    std::cout << "Valid " << n << "-bit binary numbers with more 1s than 0s in every prefix:\n";
    for (const std::string &binaryString : validBinaryStrings) {
        std::cout << binaryString << "\n";
    }
    
    return 0;
}