Given a 2d matrix and a starting position of (0,0) count all the possible paths to the target
When we look at the way we would traverse through the grid we can only move to the right or downwards. Similar to the generate subsets problem we make a choice on right or down and enumerate all the paths.
If we were to put our starting position further in the grid we see the count is a sum of all the counts to the right and all the sums below.
So we can solve this problem by moving forward in a direction and recursively getting all the counts and returning the summation. Here's how the recursion tree would look like for this -
So we need a way to stop from going over the board. We can do this by figuring out the number of columns and rows and setting up some guards
def count_paths(grid, row, col): num_col = len(grid) num_row = len(grid) # guards to prevent going over the grid if (row >= num_row) or (col >= num_col): return 0 # found our target if (row == num_row) and (col == num_col): return 1 right_count = count_paths(grid, row, col+1) left_count = count_paths(grid, row+1, col) return right_count + left_count
Finally lets look at the time and space complexity