Contar formas de expresar un número como suma de potencias

Dados dos enteros x y n, necesitamos encontrar varias formas de expresar x como suma de potencias n-ésimas de números naturales únicos. Se da que 1 <= n <= 20.
Ejemplos: 
 

Input  : x = 100
         n = 2
Output : 3
Explanation: There are three ways to 
express 100 as sum of natural numbers
raised to power 2.
100 = 10^2 = 8^2+6^2 = 1^2+3^2+4^2+5^2+7^2

Input  : x = 100
         n = 3
Output : 1
Explanation : The only combination is,
1^3 + 2^3 + 3^3 + 4^3

Usamos la recursividad para resolver el problema. Primero verificamos uno por uno si el número está incluido en la sumatoria o no. 
 

// C++ program to count number of ways
// to express x as sum of n-th power
// of unique natural numbers.
#include <bits/stdc++.h>
using namespace std;
 
// num is current num.
int countWaysUtil(int x, int n, int num)
{
    // Base cases
    int val = (x - pow(num, n));
    if (val == 0)
        return 1;
    if (val < 0)
        return 0;
 
    // Consider two possibilities, num is
    // included and num is not included.
    return countWaysUtil(val, n, num + 1) +
           countWaysUtil(x, n, num + 1);
}
 
// Returns number of ways to express
// x as sum of n-th power of two.
int countWays(int x, int n)
{
    return countWaysUtil(x, n, 1);
}
 
// Driver code
int main()
{
    int x = 100, n = 2;
    cout << countWays(x, n);
    return 0;
}

// Java program to count number of ways
// to express x as sum of n-th power
// of unique natural numbers.
public class GFG {
 
    // num is current num.
    static int countWaysUtil(int x, int n, int num)
    {
        // Base cases
        int val = (int) (x - Math.pow(num, n));
        if (val == 0)
            return 1;
        if (val < 0)
            return 0;
      
        // Consider two possibilities, num is
        // included and num is not included.
        return countWaysUtil(val, n, num + 1) +
               countWaysUtil(x, n, num + 1);
    }
      
    // Returns number of ways to express
    // x as sum of n-th power of two.
    static int countWays(int x, int n)
    {
        return countWaysUtil(x, n, 1);
    }
      
    // Driver code
    public static void main(String args[])
    {
        int x = 100, n = 2;
        System.out.println(countWays(x, n));
    }
}
// This code is contributed by Sumit Ghosh

# Python program to count number of ways
# to express x as sum of n-th power
# of unique natural numbers.
 
# num is current num.
def countWaysUtil(x,n,num):
 
    # Base cases
    val = (x - pow(num, n))
    if (val == 0):
        return 1
    if (val < 0):
        return 0
  
    # Consider two possibilities, num is
    # included and num is not included.
    return countWaysUtil(val, n, num + 1) +\
           countWaysUtil(x, n, num + 1)
 
  
# Returns number of ways to express
# x as sum of n-th power of two.
def countWays(x,n):
    return countWaysUtil(x, n, 1)
 
     
# Driver code
x = 100
n = 2
 
print(countWays(x, n))
 
# This code is contributed
# by Anant Agarwal.

// C# program to count number of ways
// to express x as sum of n-th power
// of unique natural numbers.
using System;
 
public class GFG {
 
    // num is current num.
    static int countWaysUtil(int x,
                          int n, int num)
    {
         
        // Base cases
        int val = (int) (x - Math.Pow(num, n));
        if (val == 0)
            return 1;
        if (val < 0)
            return 0;
     
        // Consider two possibilities,
        // num is included and num is
        // not included.
        return countWaysUtil(val, n, num + 1)
              + countWaysUtil(x, n, num + 1);
    }
     
    // Returns number of ways to express
    // x as sum of n-th power of two.
    static int countWays(int x, int n)
    {
        return countWaysUtil(x, n, 1);
    }
     
    // Driver code
    public static void Main()
    {
        int x = 100, n = 2;
         
        Console.WriteLine(countWays(x, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count number of ways
// to express x as sum of n-th power
// of unique natural numbers.
 
// num is current num.
function countWaysUtil($x, $n, $num)
{
     
    // Base cases
    $val = ($x - pow($num, $n));
    if ($val == 0)
        return 1;
    if ($val < 0)
        return 0;
 
    // Consider two possibilities, num is
    // included and num is not included.
    return (countWaysUtil($val, $n, $num + 1) +
            countWaysUtil($x, $n, $num + 1));
}
 
// Returns number of ways to express
// x as sum of n-th power of two.
function countWays($x, $n)
{
    return countWaysUtil($x, $n, 1);
}
 
// Driver code
$x = 100; $n = 2;
echo(countWays($x, $n));
 
// This code is contributed by Ajit.
?>

<script>
 
// JavaScript program to count number of ways
// to express x as sum of n-th power
// of unique natural numbers.
 
// num is current num.
function countWaysUtil(x, n, num)
{
    // Base cases
    let val = (x - Math.pow(num, n));
    if (val == 0)
        return 1;
    if (val < 0)
        return 0;
 
    // Consider two possibilities, num is
    // included and num is not included.
    return countWaysUtil(val, n, num + 1) +
        countWaysUtil(x, n, num + 1);
}
 
// Returns number of ways to express
// x as sum of n-th power of two.
function countWays(x, n)
{
    return countWaysUtil(x, n, 1);
}
 
// Driver code
 
    let x = 100, n = 2;
    document.write(countWays(x, n));
     
// This code is contributed by Mayank Tyagi
 
</script>

Producción: 

3

Este artículo es una contribución de Anjali . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.