logo Practice-It logo

Main Page → Problems → Solve a Problem

travel

Language/Type: Java recursion recursive backtracking
Author: Marty Stepp (on 2011/02/17)

Write a method travel that accepts integers x and y as parameters and uses recursive backtracking to print all solutions for traveling in the 2-D plane from (0, 0) to (x, y) by repeatedly using one of three moves:

  • East (E): move right 1 (increase x)
  • North (N): move up 1 (increase y)
  • Northeast (NE): move up 1 and right 1 (increase both x and y)

The following diagram shows one such path to the point (5, 3).
travel

You may assume that the x/y values passed are non-negative. If x and y are both 0, print a blank line.

The table below shows several calls to your method and the lines of output. Your lines can appear in any order; our output shown tries the possibilities in the order listed above: East, then North, then Northeast.

Call Output Call Output 
travel(1, 2);
 
E N N
N E N
N N E
N NE
NE N

travel(2, 2);
 
E E N N
E N E N
E N N E
E N NE
E NE N
N E E N
N E N E
N E NE
N N E E
N NE E
NE E N
NE N E
NE NE

travel(2, 1);
 
E E N
E N E
E NE
N E E
NE E

travel(1, 1);
 
E N
N E
NE

Hint: It may help to define a private helper method that accepts different parameters than the original method. In particular, consider building up a set of characters as a String for eventual printing. Do not use any loops in solving this problem.

Type your solution here:


This is a method problem. Write a Java method as described. Do not write a complete program or class; just the method(s) above.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.