# Combinatoric Solution explained

• Let's encode the paths as strings. The following describe valid paths for the 3 × 7 grid:

DDRRRRRR
RRRRRRDD
DRDRDDDD
...

Notice that the order in which the steps are performed doesn't matter, as long as there are 2 steps down and 6 steps to right.

More general, for the m × n problem, any permutation of Dᵐ⁻¹Rⁿ⁻¹ is a valid path. The solution is therefore the number of unique permutations of Dᵐ⁻¹Rⁿ⁻¹.

In a first step, let's ignore the uniqueness:
For m-1+n-1 elements, the number of permutations is
(m-1+n-1)! = (m+n-2)!

Now let's account for uniqueness:
There are (m-1)! ways to order the Ds, and (n-1)! ways to order the Rs in any permutation. This means, that the above figure includes (m-1)!*(n-1)! duplicates of each unique permutation. The number of unique permutations therefore is:
(m+n-2)! / ( (m-1)! *(n-1)! )

Here the Python code:

``````class Solution:
def uniquePaths(self, m, n):
return int(math.factorial(m+n-2) / (math.factorial(m-1)*math.factorial(n-1)))
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.