/** Combinations.java - recursive examples of recursion
 * @author Kees Huizing
 * @date 15 October 2010
 */

import java.util.*;
 
public class Combinations {
    int n; // number of digits of the numbers
    ArrayList<String> prefix; // not used by the parameterized calls
    Scanner input = new Scanner(System.in);
    
    // print all binary numbers of n digits
    void printNumbers() {
     System.out.println("Give length of numbers");
        n = input.nextInt();
        //variant 1
        printNumbers("");
        //variant 2
        //printNumbersWrong(new ArrayList<String>());
        //variant 3
        //printNumbers(new ArrayList<String>());        
        //variant 4
        //printNumbersU1(new ArrayList<String>());
        //variant 5
        //prefix = new ArrayList<String>(); // only used for variant 5
        //printNumbersU2();
    }
    
    // print all binary numbers of n digits starting with prefix
    // prefix is passed as String
    // uses a new String for every call
    void printNumbers(String prefix) {
        if (prefix.length()==n) {
            System.out.println(prefix);
        } else {
            printNumbers(prefix+"0");
            printNumbers(prefix+"1");
        }
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    // print all binary numbers of n digits starting with prefix
    // prefix is passed as ArrayList
    // uses a new ArrayList for all calls - doesn't work
    void printNumbersWrong(ArrayList<String> prefix) {
        if (prefix.size()>=n) {
            print(prefix);
        } else {
            prefix.add("0");
            printNumbersWrong(prefix);
            prefix.add("1");             //66
            printNumbersWrong(prefix);
        }                                //68
    }        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    // print all binary numbers of n digits starting with prefix
    // prefix is passed as ArrayList
    // uses a new ArrayList for every call 
    void printNumbers(ArrayList<String> prefix) {
        if (prefix.size()==n) {
            print(prefix);
        } else {
            ArrayList<String> p1 = new ArrayList<String>(prefix); // initialised on copy of prefix
            p1.add("0");
            printNumbers(p1);
            ArrayList<String> p2 = new ArrayList<String>(prefix); // initialised on copy of prefix  
            p2.add("1");
            printNumbers(p2);
        }
    }       
    
    
    
    
    
    
    
    
    // print all binary numbers of n digits starting with prefix
    // prefix is passed as ArrayList
    // uses the same ArrayList for all calls - with undo
    void printNumbersU1(ArrayList<String> prefix) {
        if (prefix.size()==n) {
            print(prefix);
        } else {
            prefix.add("0");
            printNumbersU1(prefix);
            prefix.remove(prefix.size()-1);
            prefix.add("1");
            printNumbers(prefix);
            prefix.remove(prefix.size()-1);
        }
    }       
    
    // print all binary numbers of n digits starting with prefix
    // prefix is instance variable
    // uses the same ArrayList for all calls - with undo
    void printNumbersU2() {
        if (prefix.size()==n) {
            print(prefix);
        } else {
            prefix.add("0");
            printNumbersU2();
            prefix.remove(prefix.size()-1);  // or prefix.set(prefix.size()-1, "1");
            prefix.add("1");                 // for these two lines
            printNumbersU2();
            prefix.remove(prefix.size()-1);        
        }
    }       
    
    void print(ArrayList<String> list) {
        for (String s : list) {
            System.out.print(s);
        }
        System.out.println();
    }
    
    public static void main(String[] a) {
        new Combinations().printNumbers();
    }
}