Algorithm for finding all paths in a NxN grid
algorithm, java
Solution
I see no indications for obstacles in your question so we can assume there are none.
Note that for an n+1 by n+1 grid, a robot needs to take exactly `2n` steps in order to reach the lower right corner. Thus, it cannot make any more than `2n` moves.
Let's start with a simpler case: [find all paths to the right down corner]
The robot can make exactly `choose(n,2n)``= (2n)!/(n!*n!)` paths: It only needs to choose which of the `2n` moves will be right, with the rest being down (there are exactly `n` of these). To generate the possible paths: just generate all binary vectors of size `2n` with exactly `n` 1's. The 1's indicate right moves, the 0's, down moves.
Now, let's expand it to all paths: First choose the length of the path. To do so, iterate over all possibilities: `0 <= i <= 2n`, where `i` is the length of the path. In this path there are `max(0,i-n) <= j <= min(i,n)` right steps. To generate all possibilities, implement the following pseudo-code:
for each i in [0,2n]:
for each j in [max(0,i-n),min(i,n)]:
print all binary vectors of size i with exactly j bits set to 1
Note 1: printing all binary vectors of size i with j bits set to 1 could be computationally expensive. That is expected since there are an exponential number of solutions. Note 2: For the case `i=2n`, you get `j in [n,n]`, as expected (the simpler case described above).
Problem
Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? I could find solution to this problem on Google, but I am not very clear with the explanations. I am trying to clearly understand the logic on how to solve this and implement in Java. Any help is appreciated. Update: This is an interview question. For now, I am trying to reach the bottom-right end and print the possible paths.