programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# finding all routes

Ranch Hand
Posts: 129
Hi all,
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.

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

Marshal
Posts: 58449
178
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.

S Ali
Ranch Hand
Posts: 129

I'm sorry it got messed up when I posted it, this is what I'm trying to achieve.

Ranch Hand
Posts: 1296
This seems like a perfect application for a recursive algorithm. Have you learned about recursion yet?

S Ali
Ranch Hand
Posts: 129
No sadly I've been trying to learn it for a couple of days now, I get confused and don't understand what to return and what to do. I would really appreciate it if you can guide me through it.

Garrett Rowe
Ranch Hand
Posts: 1296
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.

S Ali
Ranch Hand
Posts: 129
The thing is I would have to create a number of arrays representing the different routes, how can I pass them around inside the method to add to them without getting them confused .

Garrett Rowe
Ranch Hand
Posts: 1296
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.