I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.
I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.
The algorithm I wrote is a bottom-up one, as follows:
JUMP(x, y)
1. M[x-1,y+1] ← 1
2. for i=0 to x+1
M[i,y+1] ← 0
3. for i=0 to y+1
M[x+1,i] ← 0
4. for j=0 to y-1
for i=j+1 to x
M[i,j] ← 0
5. for j=y to 0
for i=j to 0
M[i,j] ← M[i+1,j] + M[i,j+1]
6. return M[i,j]
Please advise on this.