What you’re essentially doing with your binary tree is checking all possible combinations of numbers from the list `(i^n | i <- (1..x))`

. That’s quite a lot of combinations! (Exercise: how many?)

Not all of those combinations are sensible, however. For example, if x = 100 and n = 2, and you’ve already chosen, say, 4 and 5 (giving 6^{2}+7^{2}=85), then adding 8^{2}=64 is not going to help, nor is adding 9^{2}=81. In your current solution, however, you’re still checking those.

So how does one encode this knowledge in the search for solutions? The key thing is that we can build the solution recursively: we can use an already computed answer for a smaller case to help answer a larger case. If we’re given x = 10 and n = 2, then we can only add 1^{2}, 2^{2} or 3^{2}. If we try adding 3^{2}, we have only 1 left to fill, which we can only do by adding 1^{2}. If, instead, we start by trying 2^{2}, we have to make 6, which is impossible. Starting with 1^{2} lets us choose 3^{2} to fill up the remaining 9. Since only the set of numbers counts, not their order, this means there is only one solution for x=10,n=2: namely, {1^{2},3^{2}} (as stated in the problem).

Checking whether two solutions are the same modulo ordering is annoying, however. Can we do better? Yes we can, by adding another parameter to the problem.

Think about how we could do this before reading on.

A way to change the problem to prevent us from generating multiple solutions that are really the same set of numbers, is to add as a parameter the maximum value we’re allowed to choose. So a problem is now not only specified by (x=10,n=2), but also by an integer M; for example, if M=9, then we may add 1^{2}≤9, 2^{2}≤9 and 3^{2}≤9, so (x=10,n=2,M=9) has one solution: {1^{2},3^{2}}. However, (x=10,n=2,M=2) has no solutions, because by only using 1^{2} and 2^{2} you can never make 10.

How is this useful? Well, consider how we could, as a lazy office worker, go about computing how many solutions there are to (x=10,n=2,M=10). (For the original problem, we just set M=x, since choosing numbers higher than x is certainly useless.) This lazy office worker realises that either x=0, in which case we have precisely 1 solution (choosing no numbers at all), or x≠0, in which case we need to choose at least one number. If we choose, say, i^{2}, then the remainder still to fill is 10 – i^{2}. Since our lazy office worker is also clever, they realise that if we force any solutions for 10 – i^{2} to only choose numbers smaller than i^{2} (i.e. set M = i^{2} – 1), then we won’t ever get any duplicates: there may certainly be solutions for our (x,n,M) that choose i^{2} and also some larger j^{2}, but then we’ll find that one by starting with j^{2} and then going downward.

So our lazy office worker writes down a series of smaller problems: `((x-i`

, to solve for the next office worker in line. (These are recursive calls.) The total number of solutions is just the sum of the number of solutions for each of these subproblems.^{n},n,i^{n}-1) | i <- (1..M))

An alternative, more direct way to explain the same way of solving, is to note that while all solutions are sets of distinct integers, we can represent those sets by sorted lists. If the empty solution is not possible (i.e. x≠0), then each of the possible solutions for our current problem has one largest value, so we can find all solutions for the problem going over each largest value i^{n} from 1 to M, computing the solutions for (x – i^{2}, n, i^{n} – 1), and prepending that largest value i^{2} to its corresponding sub-solutions. If, instead of building the actual solution lists we just compute the number of them, we arrive at the same solution as above.

Now the above is not very formalised yet, and that is on purpose. Because for me, the next step to formalisation would be writing out the recursive function, which is 95% of the work in implementing the program. And that’s your task. 🙂

If any of the above is unclear (probably), or you get stuck, feel free to ask further questions.

EDIT: When I coded out my first solution for the problem, I also cached recursive calls in a table, making it a dynamic programming solution. However, for the given input range that apparently doesn’t help, so a standard recursive program works fine.

EDIT 2: If you want to handle `1000 1`

, then you do need dynamic programming 🙂