A banker splits a pile of n identical coins into smaller piles. Two splits are the same if they consist of the same pile sizes regardless of order: splitting 4 coins as 3+1 and 1+3 is one split. Write pile_splits(n) returning the number of distinct splits of n coins (the unsplit pile counts as one split; n = 0 has exactly one empty split).
Examples
Input: n = 4
Output: 5
Explanation: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.
Input: n = 0
Output: 1
Constraints
0 <= n <= 400- A memoised two-parameter recursion needs at most about
2nstack levels.
Goals
- Impose an ordering (largest part first) so each split is counted once
- Recurse on two parameters: the remaining total and the largest allowed part
- Memoise the pair of parameters