I also posted the problem here on Stackoverflow: http://ejj.mobi/g5i5gh but that was concerned with the programming solution. Now I am much more interested in the theory behind this problem, or rather the fact that I don't understand it.
Given two integers $X$ and $N$ how many ways can you express $X$ as a sum of the $Nth$ powers of unique natural numbers.
Compute a range of numbers $1 .. r$ where $r$ is the largest number $< X$ that could possibly be included in its sum. (i.e. for an $X$ of 10 the range would be $1..3$ because $4^2 > 10$. After finding this range I would raise it to the power of $N$ it.
From this range I computed the permutations of all subsets of $1..r$. So $1..3$ generated $,,,[1,4],[1,9],[4,9],[1,4,9]$ then the number of ways to express $X$ by powers of $N$ was simply the number of permutations that summed to $X$; in this case $[1,9]$
In my opinion this is a terrible solution: it's brute-force and inelegant, there has to be a more elegant way that uses a relationship that I can't [don't] see. Any ideas/suggestions would be appreciated.