Find ways an Integer can be expressed as sum of n | Function to calculate and return the power of any given number ; Function to check power representations recursively ; Initialize number of ways to express x as n - th powers of different natural numbers ; Calling power of ' i ' raised to 'n ; Recursively check all greater values of i ; If sum of powers is equal to x then increase the value of result . ; Return the final result ; Driver Code .
def power ( num , n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT elif ( n % 2 == 0 ) : NEW_LINE INDENT return power ( num , n // 2 ) * power ( num , n // 2 ) NEW_LINE DEDENT else : NEW_LINE INDENT return num * power ( num , n // 2 ) * power ( num , n // 2 ) NEW_LINE DEDENT DEDENT def checkRecursive ( x , n , curr_num = 1 , curr_sum = 0 ) : NEW_LINE INDENT results = 0 NEW_LINE DEDENT ' NEW_LINE INDENT p = power ( curr_num , n ) NEW_LINE while ( p + curr_sum < x ) : NEW_LINE INDENT results += checkRecursive ( x , n , curr_num + 1 , p + curr_sum ) NEW_LINE curr_num = curr_num + 1 NEW_LINE p = power ( curr_num , n ) NEW_LINE DEDENT if ( p + curr_sum == x ) : NEW_LINE INDENT results = results + 1 NEW_LINE DEDENT return results NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT x = 10 NEW_LINE n = 2 NEW_LINE print ( checkRecursive ( x , n ) ) NEW_LINE DEDENT