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