I'm going to show you how to conquer a notoriously difficult leetcode problem: Unique Paths.

And in subsequent posts I will show you how to solve: Unique Paths II (Unique Paths with BARRIERS), and Unique Paths III. So please go ahead and click +follow button on the upper right to get future updates. 👆👆

🤯

Don't worry if you're new to programming and have never solved a recursion problem in your life. I'll hold your hand and step you through it.

When I first learned recursion in high school CS class, I freaking hated it. 😖 Took me years to really understand it. My goal in this post is to cut down that learning curve for you, hopefully down to just reading THIS post!

Why Unique Paths?

Because if you understand how to solve the Unique Paths leetcode problem, you got an excellent grasp of recursion. Recursion is one of the most abstract and difficult concepts in computer science, IMHO. If you can get a deep understanding of how it works, you're head and shoulders ahead of the competition!

What the heck is Unique Path Problems Anyway?

You can read about the simplest version here. In so many words:

1. You have an m x n grid, and you're starting at position [0][0]
2. You can move only right or down
3. Your goal is to get to position [m-1][n-1], the opposite corner.

The Problem: count ALL the unique paths to go from [0][0] to [m-1][n-1].

Count what ?? Yea, if you've never seen this problem, it's a mind bender. 🤕

There are a bunch of different ways to solves this problem, even with recursion. I'm going to present a solution that easy to understand...well, was for me anyhow:

// determine paths through grid of size m x n
// starting at [y = 0][x = 0] and 
// ending at [y = m - 1][x = n - 1]
function UniquePaths(m, n, y = 0, x = 0) {

const atWallX = Boolean(x === n - 1);  //at right wall of grid
const atWallY = Boolean(y === m - 1); //at bottom wall of grid

if (atWallX && atWallY) {
  //CONGRATS you've hit the destination!!
  // add +1 to the count of unique paths
  return 1; 
  }
else if (atWallX && !atWallY) // can move down but not right
    return UniquePaths(m, n, y + 1, x);
else if (atWallY && !atWallX) // can right but not down
    return UniquePaths(m, n, y, x + 1);

else {  // => (!atWallY && !atWallX) => can move right or down
    return UniquePaths(m, n, y + 1, x) 
               + UniquePaths(m, n, y, x + 1);
  }

}

Take a Deep Breath! Let's Walk through This....

Some Context 🤓

We have a function UniquePaths(m, n, y = 0, x = 0) that going to recursively walk us through the grid, one step at a time, from y = 0, x = 0 (upper left of grid) to our final destination at y = m - 1, x = n - 1 (lower right of grid).

There are 4 arguments to UniquePaths(...): m, n, x, andy. m and n are just the fixed dimensions of the grid. x is a count of how many steps to the right we've taken (i.e. x coordinate). y is a count of how many steps down we've taken (i.e. y coordinate).

Big Picture

UniquePaths(m, n, y = 0, x = 0) will recursively walk through the grid, checking all possible paths by incrementing the value of x and y by +1 (when possible). When a path hits y = m -1, x = n - 1, it will return 1, which will go towards the count of unique paths.

If this last paragraph is confusing, don't worry. As you read the rest of this post, it will all make 100% sense.

Checking if We're Up Against a Wall

Next we define 2 Booleans which will tell us if we've against a wall (edge of the grid):

const atWallX = Boolean(x === n - 1);  //at right wall of grid
const atWallY = Boolean(y === m - 1); //at bottom wall of grid

Remember, we can only move right or down. These 2 Booleans tells us if we CAN move right in our next step (atWallX === false) or if we CAN move down in our next step (atWallY === false).

Now I know some smart ass will comment on how this is unnecessary and show us how to solve this problem in 1 line of code. Listen: there's a specific reason I'm coding the problem this way. You'll understand what I'm talking about when we work on solving the more complex Unique Code II & III leetcode problems.

Here's a hint at what I'm getting at...

😉

Time to Tango on the Grid Dance Floor

Now it's time to move either: right, down, or both:

if (atWallX && atWallY) {
  //CONGRATS you've hit the destination!!
  // add +1 to the count of unique paths
  return 1; 
  }
else if (atWallX && !atWallY) // can move down but not right
    return UniquePaths(m, n, y + 1, x);
else if (atWallY && !atWallX) // can right but not down
    return UniquePaths(m, n, y, x + 1);

else {  // => (!atWallY && !atWallX) => can move right or down
    return UniquePaths(m, n, y + 1, x) 
               + UniquePaths(m, n, y, x + 1);
  }

Here's where our Booleans REALLY come in handy.

We're going to skip the first if statement for the moment. Let's first discuss how we move through the grid first:

• if (atWallX && !atWallY) you've moved to the right as much as you can, now you can only move down, i.e. y => y + 1. We return UniquePaths(m, n, y + 1, x) with our new position: one additional step down on the grid.

• On the other hand, if (atWallY && !atWallX) then you've moved as much down as you can, and can only move right. i.e. x => x + 1. We return UniquePaths(m, n, y, x+1) with our new position: one additional step right on the grid.

The 2 Step

The last scenario is a tricky one: We're NOT against a wall. We can move either right or down. Since we're counting ALL unique paths, we need to account for BOTH scenarios.

Luckily, we have a super power with recursion: we can clone ourselves!

We can step downward: UniquePaths(m, n, y + 1, x)

While our clone steps rightward: UniquePaths(m, n, y, x + 1)

To account for the total unique paths from both combinations, we add them:

else {  // => (!atWallY && !atWallX) => can move right or down
    return UniquePaths(m, n, y + 1, x) 
               + UniquePaths(m, n, y, x + 1);
  }

Guess what? Every time we break off and clone ourselves like this, we're creating a NEW unique path! And each unique path will eventually return 1.

So imagine return UniquePaths(m, n, y + 1, x) + UniquePaths(m, n, y, x + 1), and let's say each of these UniquePaths(...) returns another return UniquePaths(m, n, y + 1, x) + UniquePaths(m, n, y, x + 1) and so on! You keep cloning yourself, over and over!

If we work through all the recursive calls, the final return statement will look something like:

return UniquePaths(m, n, ...) 
  + UniquePaths(m, n, ...)  
      +  UniquePaths(m, n, ...) 
           + UniquePaths(m, n, ...) 
              + UniquePaths(m, n, ...) 
                  + ...

####But when does it end? 😵

When we hit UniquePaths(m, n, m - 1, n - 1) we're at the lower right corner (y = m -1 and x = n - 1), finally!!

😺

Go back and look at the first if statement in the code.

This is the exit condition for our recursive calls to UniquePaths(...)...

if (atWallX && atWallY) {
  //CONGRATS you've hit the destination!!
  // add +1 to the count of unique paths
  return 1; 
  }

Once we hit the lower right corner (y = m -1 and x = n - 1), we return 1. Each of these UniquePaths(m, n, ...) will return 1:

return UniquePaths(m, n, ...) 
  + UniquePaths(m, n, ...)  
      +  UniquePaths(m, n, ...) 
           + UniquePaths(m, n, ...) 
              + UniquePaths(m, n, ...) 
                  + ...

On the final return statement, ... is actually just m - 1, n - 1. It's going to look like this:

return UniquePaths(m, n, m - 1, n - 1) 
  + UniquePaths(m, n, m - 1, n - 1)  
      +  UniquePaths(m, n, m - 1, n - 1) 
           + UniquePaths(m, n, m - 1, n - 1) 
              + UniquePaths(m, n, m - 1, n - 1) 
                  + ...

These are all the unique paths summed up! Each UniquePaths(m, n, m - 1, n - 1) is the result of the end journey of 1 path starting out at [0][0] and getting cloned every time it had the option of going right or down. Each will return 1:

return 1
  + 1
      +  1
           + 1
              + 1 
                  + ...

And THAT sum is our total count of unique paths!