# 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)…`