The task is to generate a binary string of length N using branch and bound technique Examples:
Input: N = 3 Output: 000 001 010 011 100 101 110 111 Explanation: Numbers with 3 binary digits are 0, 1, 2, 3, 4, 5, 6, 7 Input: N = 2 Output: 00 01 10 11
Approach: Generate Combinations using Branch and Bound :
- It starts with an empty solution vector.
- While Queue is not empty remove partial vector from queue.
- If it is a final vector print the combination else,
- For the next component of partial vector create k child vectors by fixing all possible states for the next component insert vectors into the queue.
Below is the implementation of the above approach
C++
// CPP Program to generate// Binary Strings using Branch and Bound#include <bits/stdc++.h>using namespace std;// Creating a Node classclass 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 nvoid 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 Codeint 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
// Java Program to generate// Binary Strings using Branch and Boundimport java.io.*;import java.util.*;// Creating a Node classclass 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); } }} |
Python3
from queue import Queue# Creating a Node classclass Node: def __init__(self, parent, level, N): self.parent = parent self.level = level self.soln = [0]*N self.child = []# Queue that maintains the list of live NodesQ = Queue()# Utility function to generate binary strings of length ndef generate(n): # If list is full print combination if n.level == N: print(''.join(str(x) for x in n.soln)) else: # Create a new list for new combination n.child = [] l = n.level # iterate while length is not equal to n for i in range(2): x = Node(n, l + 1, N) x.soln[:l] = n.soln[:l] x.soln[l] = i n.child.append(x) Q.put(x)# Driver codeif __name__ == '__main__': # Initiate Generation # Create a root Node N = 3 root = Node(None, 0, N) # Instantiate the Queue Q.put(root) while not Q.empty(): E = Q.get() generate(E) |
C#
// C# Program to generate// Binary Strings using Branch and Boundusing System;using System.Collections.Generic;// Creating a Node classpublic 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 |
Javascript
// Javascript code for the above approach// Creating a Node classclass Node { constructor(parent, level, N) { this.parent = parent; this.level = level; this.soln = new Array(N).fill(0); this.child = []; }}// Queue that maintains the list of live Nodesconst Q = [];// Utility function to generate binary strings of length nfunction generate(n, N) { // If list is full print combination if (n.level === N) { console.log(n.soln.join("")); } else { // Create a new list for new combination n.child = []; const l = n.level; // iterate while length is not equal to n for (let i = 0; i < 2; i++) { const x = new Node(n, l + 1, N); x.soln = n.soln.slice(); x.soln[l] = i; n.child.push(x); Q.push(x); } }}// Driver code(() => { // Initiate Generation // Create a root Node const N = 3; const root = new Node(null, 0, N); // Instantiate the Queue Q.push(root); while (Q.length > 0) { const E = Q.shift(); generate(E, N); }})();// This code is contributed by sdeadityasharma |
000 001 010 011 100 101 110 111
Time Complexity:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/generate-binary-strings-of-length-n-using-branch-and-bound/ […]
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/generate-binary-strings-of-length-n-using-branch-and-bound/ […]