#include <stdio.h>
// Find all binary strings that can be formed from given
// wildcard pattern
void printAllCombinations(char pattern[], int i)
{
if (pattern[i] == '\0')
{
return;
}
// if the current character is '?'
if (pattern[i] == '?')
{
for (int k = 0; k < 2; k++)
{
// replace '?' with 0 and 1
pattern[i] = k + '0';
// recuse for the remaining pattern
printAllCombinations(pattern, i + 1);
// backtrack (As array is passed by reference to the function)
// pattern[i] = '?';
}
return;
}
// if the current character is 0 or 1, ignore it and
// recuse for the remaining pattern
printAllCombinations(pattern, i + 1);
}
int main()
{
char pattern[] = "1?11?00?1?";
printAllCombinations(pattern, 0);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBGaW5kIGFsbCBiaW5hcnkgc3RyaW5ncyB0aGF0IGNhbiBiZSBmb3JtZWQgZnJvbSBnaXZlbiAKLy8gd2lsZGNhcmQgcGF0dGVybgp2b2lkIHByaW50QWxsQ29tYmluYXRpb25zKGNoYXIgcGF0dGVybltdLCBpbnQgaSkKewogICAgaWYgKHBhdHRlcm5baV0gPT0gJ1wwJykKICAgIHsKICAgICAgICBwcmludGYoIiVzXG4iLCBwYXR0ZXJuKTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgLy8gaWYgdGhlIGN1cnJlbnQgY2hhcmFjdGVyIGlzICc/JwogICAgaWYgKHBhdHRlcm5baV0gPT0gJz8nKQogICAgewogICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgMjsgaysrKQogICAgICAgIHsKICAgICAgICAgICAgLy8gcmVwbGFjZSAnPycgd2l0aCAwIGFuZCAxCiAgICAgICAgICAgIHBhdHRlcm5baV0gPSBrICsgJzAnOwogICAgICAgICAgICAKICAgICAgICAgICAgLy8gcmVjdXNlIGZvciB0aGUgcmVtYWluaW5nIHBhdHRlcm4KICAgICAgICAgICAgcHJpbnRBbGxDb21iaW5hdGlvbnMocGF0dGVybiwgaSArIDEpOwogICAgICAgICAgICAKICAgICAgICAgICAgLy8gYmFja3RyYWNrIChBcyBhcnJheSBpcyBwYXNzZWQgYnkgcmVmZXJlbmNlIHRvIHRoZSBmdW5jdGlvbikKICAgICAgICAgICAgLy8gcGF0dGVybltpXSA9ICc/JzsKICAgICAgICB9CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIC8vIGlmIHRoZSBjdXJyZW50IGNoYXJhY3RlciBpcyAwIG9yIDEsIGlnbm9yZSBpdCBhbmQgCiAgICAvLyByZWN1c2UgZm9yIHRoZSByZW1haW5pbmcgcGF0dGVybgogICAgcHJpbnRBbGxDb21iaW5hdGlvbnMocGF0dGVybiwgaSArIDEpOwp9CgppbnQgbWFpbigpCnsKICAgIGNoYXIgcGF0dGVybltdID0gIjE/MTE/MDA/MT8iOwoKICAgIHByaW50QWxsQ29tYmluYXRpb25zKHBhdHRlcm4sIDApOwoKICAgIHJldHVybiAwOwp9