Выразите X как сумму N-й степени уникальных натуральных чисел

Недавно я играл с HackerRank в свободное время, и у меня возникли проблемы с решением этой проблемы: https://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers.

Постановка задачи. Имея два целых числа X и N, найдите количество способов выразить X в виде суммы степеней N уникальных натуральных чисел. .

Пример: X = 10, N = 2

Есть только один способ получить 10, используя степени 2 меньше 10, и это 1^2 + 3^2.

Мой подход

Я знаю, что, вероятно, существует красивое, элегантное повторение этой проблемы; но, к сожалению, я не смог найти его, поэтому я начал думать о других подходах. Я решил, что я соберу диапазон чисел из [1,Z], где Z — наибольшее число, меньшее, чем X при возведении в степень N. Так что в приведенном выше примере я рассматриваю только [1,2,3], потому что 4^2 > 10 и, следовательно, не может быть частью (положительных) чисел, сумма которых равна 10. Собрав этот диапазон чисел, я возвел их все в степень N Затем найдены перестановки всех подмножеств этого списка. Итак, для [1,2,3] я нашел [[1],[4],[9],[1,4],[1,9],[4,9],[1,4,9]], а не тривиальную серию операций для больших начальных диапазонов чисел (время моего решения истекло на последних двух тестах hackerrank). Последним шагом был подсчет подсписков, сумма которых составила X.

object Solution {
    def numberOfWays(X : Int, N : Int) : Int = {
        def candidates(num : Int) : List[List[Int]] = {
            if( Math.pow(num, N).toInt > X ) 
                List.range(1, num).map(
                    l => Math.pow(l, N).toInt
                ).toSet[Int].subsets.map(_.toList).toList
            else 
                candidates(num+1)
        }
        candidates(1).count(l => l.sum == X)
    }

    def main(args: Array[String]) {
       println(numberOfWays(readInt(),readInt()))
    }
}