Genere todas las strings binarias de longitud N con el mismo recuento de 0 y 1

Dado un número entero N , la tarea es generar todas las strings binarias con ceros y unos iguales . Si no hay strings posibles, imprima -1

Ejemplos: 

Entrada : N = 2  
Salida: “01”, “10”
Explicación : Todas las strings binarias posibles de longitud 2 son: 01, 10, 11, 00. De estas, solo 2 tienen el mismo número de 0 y 1  

Entrada: 4  
Salida:  “0011”, “0101”, “0110”, “1100”, “1010”, “1001” 

 

Enfoque: La tarea se puede resolver usando recursividad. Si N es impar , entonces la respuesta es -1 , de lo contrario, podemos usar la recursividad para generar todas las strings binarias con ceros y unos iguales . Siga los pasos a continuación para resolver el problema:
 

  • Los unos variables mantienen un registro del número de 1 y los ceros variables mantienen un registro del número de 0 en la string.
  • Tanto los unos como los ceros deben tener una frecuencia N/2 .
  • Condición base: la string s almacena la string de salida . Entonces, cuando la longitud de s llega a N , detenemos las llamadas recursivas e imprimimos la string de salida s .
  • Si la frecuencia de los 1 es menor que N/2 , agregue 1 a la string e incremente en unidades .
  • Si la frecuencia de los 0 es menor que N/2 , agregue 0 a la string e incremente los ceros .

A continuación se muestra la implementación del código anterior:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function that prints
// all strings of N length with equal 1's and 0's
void binaryNum(int n, string s, int ones,
               int zeros)
{
   
    // String s contains the output to be printed
    // ones stores the frequency of 1's
    // zeros stores the frequency of 0's
    // Base Condition: When the length of string s
    // becomes N
    if (s.length() == n)
    {
        cout << (s) << endl;
        return;
    }
 
    // If frequency of 1's is less than N/2 then
    // add 1 to the string and increment ones
    if (ones < n / 2)
        binaryNum(n, s + "1", ones + 1, zeros);
 
    // If frequency of 0's is less than N/2 then
    // add 0 to the string and increment zeros
    if (zeros < n / 2)
        binaryNum(n, s + "0", ones, zeros + 1);
}
 
// Driver Code
int main()
{
 
    string s = "";
    binaryNum(4, s, 0, 0);
    return 0;
}
 
// This code is contributed by Potta Lokesh

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    // Recursive function that prints
    // all strings of N length with equal 1's and 0's
    static void binaryNum(int n, String s, int ones,
                          int zeros)
    {
        // String s contains the output to be printed
        // ones stores the frequency of 1's
        // zeros stores the frequency of 0's
        // Base Condition: When the length of string s
        // becomes N
        if (s.length() == n) {
            System.out.println(s);
            return;
        }
 
        // If frequency of 1's is less than N/2 then
        // add 1 to the string and increment ones
        if (ones < n / 2)
            binaryNum(n, s + "1", ones + 1, zeros);
 
        // If frequency of 0's is less than N/2 then
        // add 0 to the string and increment zeros
        if (zeros < n / 2)
            binaryNum(n, s + "0", ones, zeros + 1);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String s = "";
        binaryNum(4, s, 0, 0);
    }
}

Python3

# python code for the above approach
 
# Recursive function that prints
# all strings of N length with equal 1's and 0's
def binaryNum(n, s, ones, zeros):
 
    # String s contains the output to be printed
    # ones stores the frequency of 1's
    # zeros stores the frequency of 0's
    # Base Condition: When the length of string s
    # becomes N
    if (len(s) == n):
 
        print(s)
        return
 
    # If frequency of 1's is less than N/2 then
    # add 1 to the string and increment ones
    if (ones < n / 2):
        binaryNum(n, s + "1", ones + 1, zeros)
 
    # If frequency of 0's is less than N/2 then
    # add 0 to the string and increment zeros
    if (zeros < n / 2):
        binaryNum(n, s + "0", ones, zeros + 1)
 
# Driver Code
if __name__ == "__main__":
 
    s = ""
    binaryNum(4, s, 0, 0)
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
 
class GFG {
 
    // Recursive function that prints
    // all strings of N length with equal 1's and 0's
    static void binaryNum(int n, string s, int ones,
                          int zeros)
    {
        // String s contains the output to be printed
        // ones stores the frequency of 1's
        // zeros stores the frequency of 0's
        // Base Condition: When the length of string s
        // becomes N
        if (s.Length == n) {
            Console.WriteLine(s);
            return;
        }
 
        // If frequency of 1's is less than N/2 then
        // add 1 to the string and increment ones
        if (ones < n / 2)
            binaryNum(n, s + "1", ones + 1, zeros);
 
        // If frequency of 0's is less than N/2 then
        // add 0 to the string and increment zeros
        if (zeros < n / 2)
            binaryNum(n, s + "0", ones, zeros + 1);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string s = "";
        binaryNum(4, s, 0, 0);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
// javascript program for the above approach
 
   // Recursive function that prints
    // all strings of N length with equal 1's and 0's
    function binaryNum(n, s, ones, zeros)
    {
     
        // String s contains the output to be printed
        // ones stores the frequency of 1's
        // zeros stores the frequency of 0's
        // Base Condition: When the length of string s
        // becomes N
        if (s.length == n) {
            document.write(s+"<br>");
            return;
        }
 
        // If frequency of 1's is less than N/2 then
        // add 1 to the string and increment ones
        if (ones < n / 2)
            binaryNum(n, s + "1", ones + 1, zeros);
 
        // If frequency of 0's is less than N/2 then
        // add 0 to the string and increment zeros
        if (zeros < n / 2)
            binaryNum(n, s + "0", ones, zeros + 1);
    }
 
// Driver Code
var s = "";
binaryNum(4, s, 0, 0);
 
// This code is contributed by 29AjayKumar
</script>
Producción

1100
1010
1001
0110
0101
0011

Complejidad de Tiempo : O(2 N )
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por amrithabpatil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *