Java - Complex Recursive Backtracking

Question

For Java practice I started working on a method countBinary that accepts an integer n as a parameter that prints all binary numbers that have n digits in ascending order, printing each value on a separate line. Assuming n is non-negative and greater than 0, some example outputs would look like this.

I am getting pretty much nowhere with this. I am able to write a program that finds all possible letter combinations of a String and similar things, but I have been unable to make almost any progress with this specific problem using binary and integers.

Apparently the best way to go about this issue is by defining a helper method that accepts different parameters than the original method and by building up a set of characters as a String for eventual printing.

Important Note: I am NOT supposed to use for loops at all for this exercise.

Edit - Important Note: I need to have trailing 0's so that all outputs are the same length.

So far this is what I have:

public void countBinary(int n)
{
    String s = "01";
    countBinary(s, "", n);
}
private static void countBinary(String s, String chosen, int length)
{
    if (s.length() == 0)
    {
        System.out.println(chosen);
    }
    else
    {
        char c = s.charAt(0);
        s = s.substring(1);
        chosen += c;
        countBinary(s, chosen, length);
        if (chosen.length() == length)
        {
            chosen = chosen.substring(0, chosen.length() - 1);
        }
        countBinary(s, chosen, length);
        s = c + s;
    }
}

When I run my code my output looks like this.

Can anyone explain to me why my method is not running the way I expect it to, and if possible show me a solution to my issue so that I might get the correct output? Thank you!

Gene · Accepted Answer · 2015-08-09 04:28:10Z

2

There are more efficient ways to do it, but this will give you a start:

public class BinaryPrinter  {
  static void printAllBinary(String s, int n) {
    if (n == 0) System.out.println(s);
    else {
      printAllBinary(s + '0', n - 1);
      printAllBinary(s + '1', n - 1);
    }
  }

  public static void main(String [] args) {
    printAllBinary("", 4);
  }
}

I'll let you work out the more efficient way.

answered Aug 9, 2015 at 4:28

Gene

47.1k4 gold badges64 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Trafton Over a year ago

Thanks! I'll use this as a template for future questions and I'll be sure to go over it until I fully understand what you've done with recursion. You helped a lot!

Collectives™ on Stack Overflow

Java - Complex Recursive Backtracking

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related