Gorgeous! But not optimal performance.

Oh my, you're entirely correct. It was the eager calculation of all the options which slowed down my executions. This was very instructive. Pardon me.

This is non-applicable. The tests no longer allow this as a solution. They required me to do extensive caching and still ran in over six seconds. Several others have reported the steep performance requirements which did not allow such solutions.

Very well organized ideas. Readable, simple, maintainable. Splendid use of Python's features. The formatting is neat but not best practice.

O(n) runtime with a single pass, no extra copies or list resizing. ++points

This is a very interesting kata. There are trivial answers, and then there are very difficult (and more efficient) answers which could utilize advanced number theory and/or combinatorics. It's amazing just how difficult counting problems can actually be.

I think this is the optimal general solution without using dynamic programming.

Wow, impressive recursive solution. I've gotta think about this more to understand it.