c++algorithm binary combinations truthtable

Generate all possible combinations basing on binary string and under some conditions

I have to write algorithm that will generate all possible combinations of different binary strings but under some conditions. The combinations are created by: Replacing binary "1" with "00"

Other conditions:

Input binary string, if contains 0, they are in pairs always, so "00"
The output also can contain 0 only in pairs

Example:

Input:
11

Output:
001
100
0000
11

In above example, there is no 010, because as mentioned earlier, the "0" must have a pair (another "0")

Note that if given binary string contains "00", we don't change them to 1.

In other words, the algorithm should determine how many different binary strings can be created by replacing "1" with "00" (but under the conditions present above), for given binary string and returns all the possible combinations.

I tried O(n^2) algorithm, recursion but can't achieve my goal :/ That's my code:

void get_combinations(const std::string& bin, std::set<std::string>& result) {
    result.insert(bin);
    for (int i = 0; i < bin.length(); i++) {
        std::string local_combination = bin;
        for (int j = i; j < bin.length(); j++) {
            if (local_combination[j] == '1') {
                local_combination[j] = '0';
                local_combination.insert(j, "0");

                result.insert(local_combination);
            }
        }
    }
}

It works e.g. for simple input 10, 01. But for input 11, the output doesn't contain 0000. For "longer" inputs, like 1111 it gives completely bad output.

Solution

Fundamentally your combinations are built up like a tree. The units are either

    (0)               (1)
    / \       or      / \
   0                 1   00

where (.) signifies what was in the original binary string and the strings at the bottom are what you would add as a result.

So, like any binary search tree you can either do the equivalent of BFS (breadth-first-search): deal with all the possibilities at one level before moving to the next, or DFS (depth-first-search): recursively work down each branch to the bottom to insert a new combination string.

The two approaches are illustrated for your problem in the code below.

#include <iostream>
#include <string>
#include <set>
using namespace std;

//======================================================================

set<string> BFS( const string &str )
{
   set<string> result;
   if ( str.length() == 0 ) return result;

   result.insert( str.substr( 0, 1 ) );   if ( str[0] == '1' ) result.insert( "00" );
   for ( int i = 1; i < str.length(); i++ )
   {
      auto last = result;   result.clear();
      for ( const string &s : last )
      {
         result.insert( s + str[i] );
         if ( str[i] == '1' ) result.insert( s + "00" );
      }
   }
   return result;
}

//======================================================================

void DFS( const string &left, const string &right, set<string> &result )
{
   if ( right.length() == 0 )
   {
      result.insert( left );
   }
   else
   {
      DFS( left + right[0], right.substr( 1 ), result );
      if ( right[0] == '1' ) DFS( left + "00", right.substr( 1 ), result );
   }
}

//======================================================================

int main()
{
   string str;
   cout << "Enter a binary string: ";   cin >> str;

   cout << "BFS:\n";
   for ( const string &s : BFS( str ) ) cout << s << '\n';

   cout << "\nDFS:\n";
   set<string> result;
   DFS( "", str, result );
   for ( string s : result ) cout << s << '\n';
}

Output for 1111