# finding all routes

S Ali

Ranch Hand

Posts: 129

posted 6 years ago

Hi all,

I'm stuck with this problem trying to find an algorithm for it. I have a triangle like this:

I need to find all possible routes starting from the top of the triangle "1" till the bottom ,giving that I can only go left or right to the number.

For example the routes for the above triangle are:

1 1 1 1

1 1 1 2

1 1 2 2

1 2 2 2

1 2 2 3

1 2 3 3

1 2 3 4

what I did so far is implement the triangle in a two dimension array, and I did a for loop to get the following left or right number of each number of the array.

Please help I seem to be getting nowhere.

P.S :The triangle is supposed to be in a triangle shape but it gets messed up when I post it .

I'm stuck with this problem trying to find an algorithm for it. I have a triangle like this:

1

1 2

1 2 3

1 2 3 4

I need to find all possible routes starting from the top of the triangle "1" till the bottom ,giving that I can only go left or right to the number.

For example the routes for the above triangle are:

1 1 1 1

1 1 1 2

1 1 2 2

1 2 2 2

1 2 2 3

1 2 3 3

1 2 3 4

what I did so far is implement the triangle in a two dimension array, and I did a for loop to get the following left or right number of each number of the array.

Please help I seem to be getting nowhere.

P.S :The triangle is supposed to be in a triangle shape but it gets messed up when I post it .

SCJP 6

Campbell Ritchie

Sheriff

Posts: 48917

58

posted 6 years ago

What you have posted appears only to go down or right, not left or right.

You will have to be very specific about what you want; write down on a piece of paper exactly how you intend to traverse your triangle, then refine it until you have it all in very short words. Then you can try writing some code.

You will have to be very specific about what you want; write down on a piece of paper exactly how you intend to traverse your triangle, then refine it until you have it all in very short words. Then you can try writing some code.

S Ali

Ranch Hand

Posts: 129

Garrett Rowe

Ranch Hand

Posts: 1296

S Ali

Ranch Hand

Posts: 129

Garrett Rowe

Ranch Hand

Posts: 1296

posted 6 years ago

To use the recursive algorithm, you'll have to adjust your method signature somewhat to pass in the 'root' element for each recursive call. And if you want to stick with the int[][] representation of the triangle you'll need to add some helper methods to help with some of the housekeeping. But the algorithm itself is simple:

Obviously there are some details left out here, like implementations of the prependAll(), combine() and printRoutes() methods. And you'll have to figure out how to handle the recursion base case. But basically that's the meat of the entire recursive algorithm.

Edit: changed addAll() to prependAll() to more clearly express intent.

Obviously there are some details left out here, like implementations of the prependAll(), combine() and printRoutes() methods. And you'll have to figure out how to handle the recursion base case. But basically that's the meat of the entire recursive algorithm.

Edit: changed addAll() to prependAll() to more clearly express intent.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

S Ali

Ranch Hand

Posts: 129

Garrett Rowe

Ranch Hand

Posts: 1296

posted 6 years ago
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

That's the thing, you don't have to create a bunch of arrays and keep track of them. The recursion does that for you. All you have to worry about is implementing the prependAll(int, int[][]) method. It won't be the most efficient algorithm, but it will be easy to understand. A Stack<Integer> would be slightly more efficient.