The Power Sum, a recursive problem by HackerRank

Another one by HackerRank: https://www.hackerrank.com/challenges/the-power-sum:

Find the number of ways that a given integer, , can be expressed as the sum of the  power of unique, natural numbers.

Input Format

The first line contains an integer . 
The second line contains an integer .

Constraints

Output Format

Output a single integer, the answer to the problem explained above.

Sample Input 0

10
2

Sample Output 0

1

Explanation 0

If  and , we need to find the number of ways that  can be represented as the sum of squares of unique numbers.

This is the only way in which  can be expressed as the sum of unique squares.

Sample Input 1

100
2

Sample Output 1

3

Explanation 1

Sample Input 2

100
3

Sample Output 2

1

Explanation 2

 can be expressed as the sum of the cubes of . 
. There is no other way to express  as the sum of cubes.

Solution is a recursive one where we're varying the number being tested, always ensuring to increment it after adding it up to the current sum, and using as a halting criteria when the current sum surpasses the target sum. Code is down below, cheers, Marcelo.

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    static void Main(String[] args)
    {
        int x = Int32.Parse(Console.ReadLine());
        int n = Int32.Parse(Console.ReadLine());

        int solutions = 0;
        Process(0, x, 1, n, ref solutions);
        Console.WriteLine(solutions);
    }

    static void Process(int currentSum, int targetSum, int currentNumber, int n, ref int solutions)
    {
        if (currentSum == targetSum)
        {
            solutions++;
            return;
        }

        for (int i = currentNumber; currentSum + (int)Math.Pow(i, n) <= targetSum; i++)
            Process(currentSum + (int)Math.Pow(i, n), targetSum, i + 1, n, ref solutions);
    }
}