เลขฐานสองที่เป็นไปได้ทั้งหมดที่มีความยาว n ที่มีผลรวมเท่ากันในทั้งสองครึ่ง?

ที่นี่เราจะเห็นเลขฐานสองที่เป็นไปได้ทั้งหมดของ n บิต (ผู้ใช้กำหนด n) โดยที่ผลรวมของแต่ละครึ่งจะเท่ากัน ตัวอย่างเช่น หากตัวเลขคือ 10001 ที่นี่ 10 และ 01 เหมือนกันเพราะผลรวมเท่ากัน และอยู่ในส่วนต่างๆ ที่ต่างกัน เราจะสร้างตัวเลขประเภทนั้นทั้งหมด

อัลกอริทึม

genAllBinEqualSumHalf(n, ซ้าย, ขวา, ค่าต่าง)

ด้านซ้ายและขวาว่างเปล่า ส่วนต่างถือความแตกต่างระหว่างซ้ายและขวา

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);
}

ผลลัพธ์