Project Euler 719 - Number Splitting

Official link: https://projecteuler.net/problem=719

Note: I am quite happy with my solution and understanding of the problem however my code took a good 15 mins to run

Thought Process

This problem was not very easy in my opinion, it took me a long time to get a code which worked at decent speed, however there are a few speed ups which can help

All n are perfect squares so we only need to check 10^6 numbers and square them
The hardest part of this problem is to find all the partitions of a number, however this can be made easy by thinking of partitions as the length of a number
- For example the Partitions of the number 4 including permutations are
  1. 4 = [4]
  2. 3 + 1, 1 + 3 = [3, 1], [1, 3]
  3. 2 + 2 = [2, 2]
  4. 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2 = [2, 1, 1], [1, 2, 1], [1, 1, 2]
  5. 1 + 1 + 1 + 1 = [1, 1, 1, 1]
- Lets take the number 6724 in the example, because it is length 4 we can now represent all of the valid permutations extremely easily given the permutations of 4
  1. [6724]
  2. [672, 4], [6, 724]
  3. [67, 24]
  4. [67, 2 ,4], [6, 72, 4], [6, 7, 24]
  5. [6, 7, 2, 4]
A mathematical 4.5x speedup happens because we are looking for all x such that sqrt(x) = sum of the digits of x, this means we can use a modulo 9 trick

Interactive Code

Enter a number (yourinput)

Code will output sum of all S numbers less than yourinput