A recursive solution is obvious.

We can also use itertools.product and a loop.