# Leetcode 1359 Count All Valid Pickup and Delivery Options

In this Leetcode problem, we are asked to count the number of valid combinations to pickup and deliver n packages so that we always pickup a package before we deliver it.

Given

`n`

orders, each order consist in pickup and delivery services.Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).

Since the answer may be too large, return it modulo 10⁹ + 7.

## Solution

Although it is not really a computer science but a math problem, we try to resolve it by:

- Find a recursion formula
- Find a general formula if possible
- Efficiently compute the large number (use long not int!)

## Recursion formula

`countOrders(n + 1)`

= countOrders(n) * sum(valid P(n+1),D(n+1)) positions

= countOrders(n) * ((2n+1) + (2n) + ... + 1)

= countOrders(n) * (2n+1) * (2n+2) / 2

Let’s assume we know a valid combination of `P1,D1,...,Pn,Dn`

, then any valid way we insert `P(n+1)`

and `D(n+1)`

in this combination will be a valid combination for `P1,D1,...,P(n+1),D(n+1)`

. Hence `countOrders(n + 1)`

.

= countOrders(n) * sum(valid P(n+1),D(n+1)) positions

How many valid ways are there to insert `P(n+1), D(n+1)`

? If I insert `P(n+1)`

in the first position `[0]`

, then `D(n+1)`

can be placed in any of the other `2n+1`

positions. If P(n+1) is at position [1], then D(n+1) can be at any position after [1] in the array, or 2n different position. To generalize, if P(n+1) is at position i, D(n+1) can be placed in any of the positions i+1,…, 2n+1, or `2n+1 - i`

different positions. Therefore:

`countOrders(n + 1) = countOrders(n) * ((2n+1) + (2n) + ... + 1)`

This is an arithmetic sequence for which the sum is `(2n+1) * (2n+2) / 2`

. Finally:

`countOrders(n + 1) = countOrders(n) * (2n+1) * (2n+2) / 2`

## General formula

By recursion proof with `countOrders(1) = 1`

countOrders(n) = (2n)! / 2^ncountOrders(n + 1) = ((2n)! / 2^n) * ((2n+1 * 2n+2) / 2)…