Todos los números binarios posibles de longitud n con igual suma en ambas mitades

Dado un número n, necesitamos imprimir todos los números binarios de n dígitos con la misma suma en mitades izquierda y derecha. Si n es impar, entonces el elemento medio puede ser 0 o 1.
Ejemplos: 
 

Input  : n = 4
Output : 0000 0101 0110 1001 1010 1111 
Input : n = 5
Output : 00000 00100 01001 01101 01010 01110 10001 10101 10010 10110 11011 11111 

La idea es construir recursivamente las mitades izquierda y derecha y realizar un seguimiento de la diferencia entre las cuentas de 1 en ellas. Imprimimos una string cuando la diferencia se convierte en 0 y no hay más caracteres para agregar. 
 

// C++ program to generate all binary strings with
// equal sums in left and right halves.
#include <bits/stdc++.h>
using namespace std;
 
/* Default values are used only in initial call.
   n is number of bits remaining to be filled
   di is current difference between sums of
      left and right halves.
   left and right are current half substrings. */
void equal(int n, string left="", string right="",
                                        int di=0)
{
    // TWO BASE CASES
    // If there are no more characters to add (n is 0)
    if (n == 0)
    {
        // If difference between counts of 1s and
        // 0s is 0 (di is 0)
        if (di == 0)
            cout << left + right << " ";
        return;
    }
 
    /* If 1 remains than string length was odd */
    if (n == 1)
    {
        // If difference is 0, we can put remaining
        // bit in middle.
        if (di == 0)
        {
            cout << left + "0" + right << " ";
            cout << left + "1" + right << " ";
        }
        return;
    }
 
    /* If difference is more than what can be
       be covered with remaining n digits
       (Note that lengths of left and right
        must be same) */
    if ((2 * abs(di) <= n))
    { 
         
         /* add 0 to end in both left and right
         half. Sum in both half will not
               change*/
         equal(n-2, left+"0", right+"0", di);
 
         /* add 0 to end in both left and right
         half* subtract 1 from di as right
         sum is increased by 1*/
         equal(n-2, left+"0", right+"1", di-1);
 
        /* add 1  in end in left half and 0 to the
        right half. Add 1 to di as left sum is
        increased by 1*/
        equal(n-2, left+"1", right+"0", di+1);
 
        /* add 1 in end to both left and right
          half the sum will not change*/
        equal(n-2, left+"1", right+"1", di);
    }
}
 
/* driver function */
int main()
{
    int n = 5; // n-bits
    equal(n);
    return 0;
}

// Java program to generate all binary strings
// with equal sums in left and right halves.
import java.util.*;
 
class GFG
{
 
// Default values are used only in initial call.
// n is number of bits remaining to be filled
// di is current difference between sums of
// left and right halves.
// left and right are current half substrings.
static void equal(int n, String left,
                         String right, int di)
{
    // TWO BASE CASES
    // If there are no more characters to add (n is 0)
    if (n == 0)
    {
        // If difference between counts of 1s and
        // 0s is 0 (di is 0)
        if (di == 0)
            System.out.print(left + right + " ");
        return;
    }
 
    /* If 1 remains than string length was odd */
    if (n == 1)
    {
        // If difference is 0, we can put
        // remaining bit in middle.
        if (di == 0)
        {
            System.out.print(left + "0" + right + " ");
            System.out.print(left + "1" + right + " ");
        }
        return;
    }
 
    /* If difference is more than what can be
    be covered with remaining n digits
    (Note that lengths of left and right
     must be same) */
    if ((2 * Math.abs(di) <= n))
    {
         
            // add 0 to end in both left and right
            // half. Sum in both half will not
            // change
            equal(n - 2, left + "0", right + "0", di);
 
            // add 0 to end in both left and right
            // half* subtract 1 from di as right
            // sum is increased by 1
            equal(n - 2, left + "0", right + "1", di - 1);
         
 
        // add 1 in end in left half and 0 to the
        // right half. Add 1 to di as left sum is
        // increased by 1*
        equal(n - 2, left + "1", right + "0", di + 1);
 
        // add 1 in end to both left and right
        // half the sum will not change
        equal(n - 2, left + "1", right + "1", di);
    }
}
 
// Driver Code
public static void main(String args[])
{
    int n = 5;
     
    // n-bits
    equal(n, "", "", 0);
}
}
 
// This code is contributed
// by SURENDRA_GANGWAR

# Python program to generate all binary strings with
# equal sums in left and right halves.
 
# Default values are used only in initial call.
# n is number of bits remaining to be filled
# di is current difference between sums of
# left and right halves.
# left and right are current half substrings.
def equal(n: int, left = "", right = "", di = 0):
 
    # TWO BASE CASES
    # If there are no more characters to add (n is 0)
    if n == 0:
 
        # If difference between counts of 1s and
        # 0s is 0 (di is 0)
        if di == 0:
            print(left + right, end = " ")
        return
 
    # If 1 remains than string length was odd
    if n == 1:
 
        # If difference is 0, we can put remaining
        # bit in middle.
        if di == 0:
            print(left + "0" + right, end = " ")
            print(left + "1" + right, end = " ")
        return
 
    # If difference is more than what can be
    # be covered with remaining n digits
    # (Note that lengths of left and right
    # must be same)
    if 2 * abs(di) <= n:
      
        # add 0 to end in both left and right
        # half. Sum in both half will not
        # change
        equal(n - 2, left + "0", right + "0", di)
 
        # add 0 to end in both left and right
        # half* subtract 1 from di as right
        # sum is increased by 1
        equal(n - 2, left + "0", right + "1", di - 1)
 
        # add 1 in end in left half and 0 to the
        # right half. Add 1 to di as left sum is
        # increased by 1
        equal(n - 2, left + "1", right + "0", di + 1)
 
        # add 1 in end to both left and right
        # half the sum will not change
        equal(n - 2, left + "1", right + "1", di)
 
# Driver Code
if __name__ == "__main__":
    n = 5 # n-bits
    equal(5)
 
# This code is contributed by
# sanjeev2552

// C# program to generate all binary strings
// with equal sums in left and right halves.
using System;
 
class GFG
{
 
// Default values are used only in initial call.
// n is number of bits remaining to be filled
// di is current difference between sums of
// left and right halves.
// left and right are current half substrings.
static void equal(int n, String left,
                         String right, int di)
{
    // TWO BASE CASES
    // If there are no more characters
    // to add (n is 0)
    if (n == 0)
    {
        // If difference between counts of 1s
        // and 0s is 0 (di is 0)
        if (di == 0)
            Console.Write(left + right + " ");
        return;
    }
 
    /* If 1 remains than string length was odd */
    if (n == 1)
    {
        // If difference is 0, we can put
        // remaining bit in middle.
        if (di == 0)
        {
            Console.Write(left + "0" +
                          right + " ");
            Console.Write(left + "1" +
                          right + " ");
        }
        return;
    }
 
    /* If difference is more than what can be
    be covered with remaining n digits
    (Note that lengths of left and right
    must be same) */
    if ((2 * Math.Abs(di) <= n))
    {
 
         
            // add 0 to end in both left and right
            // half. Sum in both half will not
            // change
            equal(n - 2, left + "0", right + "0", di);
 
            // add 0 to end in both left and right
            // half* subtract 1 from di as right
            // sum is increased by 1
            equal(n - 2, left + "0",
                  right + "1", di - 1);
         
 
        // add 1 in end in left half and 0 to the
        // right half. Add 1 to di as left sum is
        // increased by 1*
        equal(n - 2, left + "1",
              right + "0", di + 1);
 
        // add 1 in end to both left and right
        // half the sum will not change
        equal(n - 2, left + "1", right + "1", di);
    }
}
 
// Driver Code
public static void Main(String []args)
{
    int n = 5;
     
    // n-bits
    equal(n, "", "", 0);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to generate all binary strings
// with equal sums in left and right halves.
 
// Default values are used only in initial call.
// n is number of bits remaining to be filled
// di is current difference between sums of
// left and right halves.
// left and right are current half substrings.
function equal(n,left,right,di)
{
    // TWO BASE CASES
    // If there are no more characters to add (n is 0)
    if (n == 0)
    {
        // If difference between counts of 1s and
        // 0s is 0 (di is 0)
        if (di == 0)
            document.write(left + right + " ");
        return;
    }
   
    /* If 1 remains than string length was odd */
    if (n == 1)
    {
        // If difference is 0, we can put
        // remaining bit in middle.
        if (di == 0)
        {
            document.write(left + "0" + right + " ");
            document.write(left + "1" + right + " ");
        }
        return;
    }
   
    /* If difference is more than what can be
    be covered with remaining n digits
    (Note that lengths of left and right
     must be same) */
    if ((2 * Math.abs(di) <= n))
    {
           
            // add 0 to end in both left and right
            // half. Sum in both half will not
            // change
            equal(n - 2, left + "0", right + "0", di);
   
            // add 0 to end in both left and right
            // half* subtract 1 from di as right
            // sum is increased by 1
            equal(n - 2, left + "0", right + "1", di - 1);
           
   
        // add 1 in end in left half and 0 to the
        // right half. Add 1 to di as left sum is
        // increased by 1*
        equal(n - 2, left + "1", right + "0", di + 1);
   
        // add 1 in end to both left and right
        // half the sum will not change
        equal(n - 2, left + "1", right + "1", di);
    }
}
 
// Driver Code
let n = 5;
 
// n-bits
equal(n, "", "", 0);
 
 
// This code is contributed by rag2127
 
</script>

Producción:  

10001 10101 10010 10110 11011 11111 

Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.