समान योग वाले दोनों आधे भागों की लंबाई n की सभी संभावित बाइनरी संख्याएं

यहां हम n बिट (n उपयोगकर्ता द्वारा दिया गया) की सभी संभावित बाइनरी संख्याएं देखेंगे जहां प्रत्येक आधे का योग समान है। उदाहरण के लिए, यदि संख्या 10001 है तो यहां 10 और 01 समान हैं क्योंकि उनका योग समान है, और वे अलग-अलग आधे में हैं। यहां हम उस प्रकार की सभी संख्याएं उत्पन्न करेंगे।

एल्गोरिदम

genAllBinEqualSumHalf(n, left, right, diff)

left और right प्रारंभ में खाली हैं, diff बाएं और दाएं के बीच का अंतर रखता है।

शुरुआत
    यदि n 0 है, तो
        यदि diff 0 है, तो
            left + right प्रिंट करें
        यदि समाप्त
        वापस करें
    यदि समाप्त
    यदि n 1 है, तो
        यदि diff 0 है, तो
            left + 0 + right प्रिंट करें
            left + 1 + right प्रिंट करें
        यदि समाप्त
        वापस करें
    यदि समाप्त
    यदि 2*|diff| <= n, तो
        यदि left खाली नहीं है, तो
            genAllBinEqualSumHalf(n-2, left+0, right+0, diff)
            genAllBinEqualSumHalf(n-2, left+0, right+1, diff-1)
        यदि समाप्त
        genAllBinEqualSumHalf(n-2, left+1, right+0, diff+1)
        genAllBinEqualSumHalf(n-2, left+1, right+1, diff)
    यदि समाप्त
समाप्त

उदाहरण

#include <bits/stdc++.h>
using namespace std;

void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) {
    if (n == 0) {
        if (di == 0)
            cout << left + right << " ";
        return;
    }
    if (n == 1) {
        if (di == 0) {
            cout << left + "0" + right << " ";
            cout << left + "1" + right << " ";
        }
        return;
    }
    if ((2 * abs(di) <= n)) {
        if (left != "") {
            genAllBinEqualSumHalf(n-2, left+"0", right+"0", di);
            genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
        }
        genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1);
        genAllBinEqualSumHalf(n-2, left+"1", right+"1", di);
    }
}

int main() {
    int n = 5;
    genAllBinEqualSumHalf(n);
    return 0;
}

आउटपुट

100001 100010 101011 110011 100100 101101 101110 110101 110110 111111