Number of Paths (BackTracking) in Java Illustration


  You're testing a new driverless car that is located at the Southwest
  (bottom-left) corner of an n×n grid. The car is supposed to get to the
  opposite, Northeast (top-right), corner of the grid. Given n, the size
  of the grid’s axes, write a function numOfPathsToDest that returns
  the number of the possible paths the driverless car can take.
  
  For convenience, let's represent every square in the grid as a pair
  (i,j). The first coordinate in the pair denotes the east-to-west axis,
  and the second coordinate denotes the south-to-north axis. The initial
  state of the car is (0,0), and the destination is (n-1,n-1).
  
  The car must abide by the following two rules: it cannot cross the
  diagonal border. In other words, in every step the position (i,j)
  needs to maintain i >= j. See the illustration above for n = 5. In
  every step, it may go one square North (up), or one square East
  (right), but not both. E.g. if the car is at (3,1), it may go to (3,2)
  or (4,1).


Example

input:  n = 4

output: 5 # since there are five possibilities:
          # “EEENNN”, “EENENN”, “ENEENN”, “ENENEN”, “EENNEN”,
          # where the 'E' character stands for moving one step
          # East, and the 'N' character stands for moving one step
          # North (so, for instance, the path sequence “EEENNN”
          # stands for the following steps that the car took:
          # East, East, East, North, North, North)


My approach:

import java.io.*;
import java.util.*;

class Solution {

  static int numOfPathsToDest(int n) {
    // your code goes here
    //n = 2
    int startX = 0;
    int startY = 0;


    int numPoss = numPaths(startX,startY,n);


    return numPoss;


  }

  static private int numPaths(int startX, int startY, int n )
  {
    int destX = n - 1;
    int destY = n - 1;
    int numPoss = 0;

    //Base case
    if((startX == destX) &amp;&amp; (startY == destY ))
      numPoss++;

    //Recursive condition
    else 
      {
        if( (startX &gt;= startY) &amp;&amp; (startX &lt; n) &amp;&amp; ( startY &lt; n ))
        {
          //East 
          numPoss += numPaths(startX+1, startY,n);

          //North
           numPoss +=  numPaths(startX,startY + 1, n);
        } 

        //Time complexity: O(2^n) -&gt; O(n^2) in memoization
       //Space complexity: O(n^2)
      //Bottom up approach: O(n) space complexity
      //Time complexity: O(n)
      }

    return numPoss;
  }

  public static void main(String[] args) {
    System.out.println(numOfPathsToDest(2));
  }

}

//n = 4
//#squares = 4 + 3 + 2 + 1

//#squares = n + n-1 + n-2 + ... 1 = n(n + 1)/2

//square 0 - eastx 4/ n - 1 

//square (1,0): up - 1, east -  3/(n - 1)

//square (2,0): up - 2, east: 2/(n - 2)

//east + north : n 
//


I have the following questions with respect to the code:


What can I further improve my code in terms of space and time complexity?
Is there any smarter approach to solve this question?
Does my code violate any of the coding conventions?
Are there any other ways that I can further optimize the code?


Reference
I have a feeling there is a direct way to compute this amount, but I am not really into all the mathematics, you could possibly look it up. I'll talk about your code as is:


You should really remove all the superfluous white space, it hampers readability.
In Java, opening braces are not on a new line.
private before static.
Do not save te result of your recursive function in a variable, you can return at once.
The problem states you move from (0, 0) to (n,n). If you model your code the other way around, you can simplify it quite a bit. No need to pass n to your recursive function for example, as you can simply compare with 0.
Try to always use braces, even if you only have one line inside the block, as for example with the if part in your recursive function. It helps prevent unnoticed bugs due to formatting, and helps ease up modifying it later on.
In the else block, you do not need to check if x and y are valid, if you check for 0 up front.
In the recursive function, if the initial if succeeds, the result will always be 1. So you can return at once, it makes it more readable. Return early is a good thing in my opinion. The variable can then be put inside the else, reducing the scope.
You mention memoization, yet you do not seem to be using it. If you take the example, and the paths taken there:

“EEENNN”

“EEN|ENN”
“EEN|NEN”

“ENE|NEN”
“ENE|ENN”



Note that EEN will bring you to the same spot as ENE. You can see that each of those share the same second parts as well. This is duplication which we can use to speed up the algorithm.

If you think about it, there are generally multiple ways to get to some point (x,y). If you think of this as the starting point, the possible paths to the destination will obviously be the same, no matter how you get there. So what you can do is create a lookup table for a calculated location, so you calculate each one only once. This will give you an extreme amount of speedup I would think, on problems with a big amount of possible paths. Which you will get to quickly, even for small values of n.