Recursion: Given a number, count the number of ways to express a number as sum of powers.

Problem Statement:

You are given 2 numbers, x and n.

You need to find the number of ways to express x as a sum of nth powers of unique natural numbers.

Given that 1 <= n <= 20.

Example:

Input:

x = 100
n = 2

Output: 3

Why ?

THere are 3 ways to express 100 as a sum of natural numbers raised to power of 2.

100 = 10^2

100 = 8^2 + 6^2

100 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2 

Solution Explanation:

We will use recursion to solve this problem.

Code Solution

#include <iostream>
#include <cmath>
using namespace std;

int solution(int x, int n, int num)
{
    // Base cases
    int val = (x - pow(num, n));
    
    if (val == 0)
        return 1;
    if (val < 0)
        return 0;

    return solution(val, n, num + 1) +
           solution(x, n, num + 1);
}

int main()
{
    int x = 100, n = 2;
    cout << solution(x, n, 1);
    return 0;
}

Output

3