Thought Process

Extremely similar to Problem 172 and Problem 164 for me, been going through the 150-200s and wow there is a lot of recursion.

This time my function looks like this:

recursion(goal, pos, prev, mask)

1. If pos = 0

   • Pick a number, x, 1 to 9 to start us off

   • total += recursion(goal, 1, x, mask | 2**x)

2. If pos = goal:

   • if mask = (1 << 11) - 1 (This is the same as 11,111,111,111 in binary)

3. Otherwise if prev > 0

   • total += recursion(goal, pos + 1, prev - 1, mask | 2**(prev - 1))

4. If prev < 9:

   • total += recursion(goal, pos + 1, prev + 1, mask | 2**(prev + 1))

Then we just perform recursion(10, 0, 0, (1 << 10)) + recursion(11, 0, 0, (1 << 10)) + ... + recursion(40, 0, 0, (1 << 10)) and thats the answer!

Explanation on mask:

I'm using a bit mask, (1 << 10) = 1024 = 10,000,000,000 in binary, if I have a number say 7 in my number then I flip the bit at the 8th position (because we have 0th position), then 1024 | 2**7 = 1152 = 10,010,000,000. So if we have all 10 numbers our mask should be equal to 11,111,111,111 = 2047 = (1 << 11) - 1

Used the @cache decorator from functools for memoization, get the solution instantly!