Question

How to generate all binary combination of size k with no consecutive 1's in C++

Answer 1

#include <iostream>

void create_combination(int k, char str[], int i) {
    if (i == k) {
        str[i] = '\0';
        std::cout << str << " ";
        return;
    }
    
    if (str[i - 1] == '1') {
        str[i]='0';
        create_combination(k, str, i + 1);
    }
    
    if (str[i - 1] == '0') {
        str[i] = '0';
        create_combination(k, str, i + 1);
        str[i] = '1';
        create_combination(k, str, i + 1) ;
    }
}
 
void binary_combinations(int k) {
    if (k <= 0) {
        return;
    }
    
    char str[32];
    
    str[0] = '0' ;
    create_combination(k, str, 1) ;
    str[0] = '1';
    create_combination(k, str, 1);
}
 
int main()
{
    int k = 4;
    
    binary_combinations(k);
}




/*
run:

0000 0001 0010 0100 0101 1000 1001 1010 

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>

void generate_binary_combination(int k, int i, std::string str) {
    if (k == 0) {
        std::cout << str << " ";
        return;
    }

    if (str.size() > 0 && str[str.size() - 1] == '1') {
        generate_binary_combination(k - 1, i, str + "0");
    } else {
        generate_binary_combination(k - 1, i, str + "0");
        if (i > 0) {
            generate_binary_combination(k - 1, i - 1, str + "1");
        }
    }
}

int main() {
    int k = 4, i = 2;
    std::string str = "";
    
    generate_binary_combination(k, i, str);
}




/*
run:

0000 0001 0010 0100 0101 1000 1001 1010 

*/

 

70+ SQL courses for beginners and professionals