উভয় অর্ধে সমান যোগফল n দৈর্ঘ্যের সমস্ত সম্ভাব্য বাইনারি সংখ্যা?

এখানে আমরা n বিটের সম্ভাব্য সমস্ত বাইনারি সংখ্যা দেখতে পাব (n ব্যবহারকারী দ্বারা দেওয়া হয়েছে) যেখানে প্রতিটি অর্ধেক এর যোগফল একই। উদাহরণস্বরূপ, যদি সংখ্যাটি 10001 হয় এখানে 10 এবং 01 একই কারণ তাদের যোগফল একই, এবং তারা বিভিন্ন অর্ধেকের মধ্যে রয়েছে। এখানে আমরা সেই ধরণের সমস্ত সংখ্যা তৈরি করব।

অ্যালগরিদম

genAllBinEqualSumHalf(n, left, right, diff)

বাম এবং ডান প্রাথমিকভাবে খালি, ডিফ বাম এবং ডানের মধ্যে পার্থক্য ধরে রাখে

Begin
   if n is 0, then
      if diff is 0, then
         print left + right
      end if
      return
   end if
   if n is 1, then
      if diff is 0, then
         print left + 0 + right
         print left + 1 + right
      end if
      return
   end if
   if 2* |diff| <= n, then
      if left is not blank, then
         genAllBinEqualSumHalf(n-2, left + 0, right + 0, diff)
         genAllBinEqualSumHalf(n-2, left + 0, right + 1, diff-1)
      end if
      genAllBinEqualSumHalf(n-2, left + 1, right + 0, diff + 1)
      genAllBinEqualSumHalf(n-2, left + 1, right + 1, diff)
   end if
End

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
//left and right strings will be filled up, di will hold the difference between left and right
void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) {
   if (n == 0) { //when the n is 0
      if (di == 0) //if diff is 0, then concatenate left and right
         cout << left + right << " ";
      return;
   }
   if (n == 1) {//if 1 bit number is their
      if (di == 0) { //when difference is 0, generate two numbers one with 0 after left, another with 1 after left, then add right
         cout << left + "0" + right << " ";
         cout << left + "1" + right << " ";
      }
      return;
   }
   if ((2 * abs(di) <= n)) {
      if (left != ""){ //numbers will not start with 0
         genAllBinEqualSumHalf(n-2, left+"0", right+"0", di);
         //add 0 after left and right
         genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
         //add 0 after left, and 1 after right, so difference is 1 less
      }
      genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1); //add 1 after left, and 0 after right, so difference is 1 greater
      genAllBinEqualSumHalf(n-2, left+"1", right+"1", di); //add 1 after left and right
   }
}
main() {
   int n = 5;
   genAllBinEqualSumHalf(n);
}

আউটপুট