Question

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

Answer 1

public class Program {
    private static void create_combination(int k, char str[], int i) {
        if (i == k) {
            System.out.print(str);
            System.out.print(" ");
            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);
        }
    }
     
    private static void binary_combinations_with_no_consecutive_1(int k) {
        if (k <= 0) {
            return;
        }
     
        char str[] = new char[k];
         
        str[0]= '0';
        create_combination(k, str, 1);
         
        str[0] = '1';
        create_combination(k, str, 1);
    }
     
    public static void main(String args[]) {
        int k = 4;
 
        binary_combinations_with_no_consecutive_1(k);
    }
}
 
 
 
 
/*
run:
  
0000 0001 0010 0100 0101 1000 1001 1010 
  
*/

 

70+ SQL courses for beginners and professionals

Answer 2

public class Program {
    private static void binary_combinations_with_no_consecutive_1(int k, int i, String str) {
    	if (k == 0) {
    		System.out.print(str + " ");
    		return;
    	}
    
    	if (str.length() > 0 && str.charAt(str.length() - 1) == '1') {
    		binary_combinations_with_no_consecutive_1(k - 1, i, str + "0");
    	}
    	else {
    		binary_combinations_with_no_consecutive_1(k - 1, i, str + "0");
    		if (i > 0) {
    			binary_combinations_with_no_consecutive_1(k - 1, i - 1, str + "1");
    		}
    	}
    }
    
    public static void main(String[] args) 
    {
        int k = 4;
	    int i = 2;
	    String str = "";

	    binary_combinations_with_no_consecutive_1(k, i, str);
    } 
}



/*
run:
 
0000 0001 0010 0100 0101 1000 1001 1010 
 
*/

 

70+ SQL courses for beginners and professionals