All possible binary numbers of length n with equal sum in both halves?

Here we will see all possible binary numbers of n bit (n is given by the user) where the sum of each half is same. For example, if the number is 10001 here 10 and 01 are same because their sum is same, and they are in the different halves. Here we will generate all numbers of that type.

Algorithm

genAllBinEqualSumHalf(n, left, right, diff)

left and right are initially empty, diff is holding difference between left and right

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

Example

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

Output

100001 100010 101011 110011 100100 101101 101110 110101 110110 111111