Genere strings binarias de longitud N usando Branch and Bound

La tarea es generar una string binaria de longitud N utilizando la técnica de ramificación y límite

Ejemplos:

Entrada: N = 3
Salida:
000
001
010
011
100
101
110
111
Explicación:
Los números con 3 dígitos binarios son
0, 1, 2, 3, 4, 5, 6, 7

Entrada: N = 2
Salida:
00
01
10
11

Acercarse:

Genere combinaciones usando Branch and Bound:

• Comienza con un vector solución vacío .
• Mientras la cola no esté vacía, elimine el vector parcial de la cola.
• Si es un vector final imprima la combinación de lo contrario,
• Para el siguiente componente del vector parcial, cree k vectores secundarios fijando todos los estados posibles para el siguiente componente insertando vectores en la cola.

A continuación se muestra la implementación del enfoque anterior.

// CPP Program to generate
// Binary Strings using Branch and Bound
#include <bits/stdc++.h>
using namespace std;
  
// Creating a Node class
class Node
{
public:
    int *soln;
    int level;
    vector<Node *> child;
    Node *parent;
  
    Node(Node *parent, int level, int N)
    {
        this->parent = parent;
        this->level = level;
        this->soln = new int[N];
    }
};
  
// Utility function to generate binary strings of length n
void generate(Node *n, int &N, queue<Node *> &Q)
{
    // If list is full print combination
    if (n->level == N)
    {
        for (int i = 0; i < N; i++)
            cout << n->soln[i];
        cout << endl;
    }
    else
    {
        int l = n->level;
  
        // iterate while length is not equal to n
        for (int i = 0; i <= 1; i++)
        {
            Node *x = new Node(n, l + 1, N);
            for (int k = 0; k < l; k++)
                x->soln[k] = n->soln[k];
            x->soln[l] = i;
            n->child.push_back(x);
            Q.push(x);
        }
    }
}
  
// Driver Code
int main()
{
    // Initiate Generation
    // Create a root Node
    int N = 3;
    Node *root;
    root = new Node(NULL, 0, N);
  
    // Queue that maintains the list of live Nodes
    queue<Node *> Q;
      
    // Instantiate the Queue
    Q.push(root);
  
    while (!Q.empty())
    {
        Node *E = Q.front();
        Q.pop();
        generate(E, N, Q);
    }
  
    return 0;
}
  
// This code is contributed by
// sanjeev2552

// Java Program to generate
// Binary Strings using Branch and Bound
  
import java.io.*;
import java.util.*;
  
// Creating a Node class
class Node {
  
    int soln[];
    int level;
    ArrayList<Node> child;
    Node parent;
  
    Node(Node parent, int level, int N)
    {
        this.parent = parent;
        this.level = level;
        this.soln = new int[N];
    }
}
  
class GFG {
  
    static int N;
  
    // Queue that maintains the list of live Nodes
    public static Queue<Node> Q;
  
    // Utility function to generate binary strings of length n
    public static void generate(Node n)
    {
        // If list is full print combination
        if (n.level == N) {
            for (int i = 0; i <= N - 1; i++) {
                System.out.print(n.soln[i]);
            }
            System.out.println();
        }
        else {
  
            // Create a new vector for new combination
            n.child = new ArrayList<Node>();
  
            int l = n.level;
  
            // iterate while length is not equal to n
            for (int i = 0; i <= 1; i++) {
                Node x = new Node(n, l + 1, N);
                for (int k = 0; k < l; k++) {
                    x.soln[k] = n.soln[k];
                }
                x.soln[l] = i;
                n.child.add(x);
                Q.add(x);
            }
        }
    }
  
    // Driver code
    public static void main(String args[])
    {
        // Initiate Generation
        // Create a root Node
        N = 3;
        Node root = new Node(null, 0, N);
  
        // Instantiate the Queue
        Q = new LinkedList<Node>();
        Q.add(root);
  
        while (Q.size() != 0) {
            Node E = Q.poll();
            generate(E);
        }
    }
}

// C# Program to generate
// Binary Strings using Branch and Bound
using System;
using System.Collections.Generic;
  
// Creating a Node class
public class Node 
{
    public int []soln;
    public int level;
    public List<Node> child;
    public Node parent;
  
    public Node(Node parent, 
                int level, int N)
    {
        this.parent = parent;
        this.level = level;
        this.soln = new int[N];
    }
}
  
class GFG
{
    static int N;
  
    // Queue that maintains the list of live Nodes
    public static Queue<Node> Q;
  
    // Utility function to generate 
    // binary strings of length n
    public static void generate(Node n)
    {
        // If list is full print combination
        if (n.level == N)
        {
            for (int i = 0; i <= N - 1; i++)
            {
                Console.Write(n.soln[i]);
            }
            Console.WriteLine();
        }
        else
        {
  
            // Create a new vector for new combination
            n.child = new List<Node>();
  
            int l = n.level;
  
            // iterate while length is not equal to n
            for (int i = 0; i <= 1; i++) 
            {
                Node x = new Node(n, l + 1, N);
                for (int k = 0; k < l; k++) 
                {
                    x.soln[k] = n.soln[k];
                }
                x.soln[l] = i;
                n.child.Add(x);
                Q.Enqueue(x);
            }
        }
    }
  
    // Driver code
    public static void Main(String []args)
    {
        // Initiate Generation
        // Create a root Node
        N = 3;
        Node root = new Node(null, 0, N);
  
        // Instantiate the Queue
        Q = new Queue<Node>();
        Q.Enqueue(root);
  
        while (Q.Count != 0)
        {
            Node E = Q.Dequeue();
            generate(E);
        }
    }
}
  
// This code is contributed by Rajput-Ji

000
001
010
011
100
101
110
111

Complejidad del tiempo: