title: All possible paths in n*n matrix - python
body: <p>I am trying to solve a interview question: </p>
  
  <blockquote>
    <p>Given a n*n matrix, assume you are starting at top-left cell(i.e. 0,0). You are allowed to move either right or down and you have to travel to the bottom right cell. Get the maximum value less than the given value. For example, assume 3*3 matrix, given value is <code>5</code>.</p>
  </blockquote>
  
  <pre><code>0 1 2
  2 1 2
  3 2 1
  
  optimal path is 0 -&gt; 1 -&gt; 1 -&gt; 2 -&gt; 1 = 5
  </code></pre>
  
  <p>I started coding using recursion but the answer is not correct. Any suggestions?</p>
  
  <pre><code>def findAllPaths(currX, currY, path, grid, sum):
      #print currX, currY
      if currX == len(grid)-1:
          i = currY
          temp = 0
          while i &lt; len(grid):
              path = path + str(grid[currX][i])
              temp += grid[currX][i]
              i += 1
          sum.append(temp)
          #print 'first loop', sum, path
          return
      if currY == len(grid)-1:
          i = currX
          temp = 0
          while i &lt; len(grid):
              path = path + str(grid[i][currY])
              temp += grid[i][currY]
              i += 1
          sum.append(temp)
          #print 'second loop', sum, path
          return
      #print currX, currY
      #path = path + str(grid[currX][currY])
      findAllPaths(currX+1,currY,path,grid, sum)
      findAllPaths(currX, currY+1,path,grid, sum)
  
      return sum
  </code></pre>