backtracking.power_sum
======================

.. py:module:: backtracking.power_sum

.. autoapi-nested-parse::

   Problem source: https://www.hackerrank.com/challenges/the-power-sum/problem
   Find the number of ways that a given integer X, can be expressed as the sum
   of the Nth powers of unique, natural numbers. For example, if X=13 and N=2.
   We have to find all combinations of unique squares adding up to 13.
   The only solution is 2^2+3^2. Constraints: 1<=X<=1000, 2<=N<=10.



Functions
---------

.. autoapisummary::

   backtracking.power_sum.backtrack
   backtracking.power_sum.solve


Module Contents
---------------

.. py:function:: backtrack(needed_sum: int, power: int, current_number: int, current_sum: int, solutions_count: int) -> tuple[int, int]

   >>> backtrack(13, 2, 1, 0, 0)
   (0, 1)
   >>> backtrack(10, 2, 1, 0, 0)
   (0, 1)
   >>> backtrack(10, 3, 1, 0, 0)
   (0, 0)
   >>> backtrack(20, 2, 1, 0, 0)
   (0, 1)
   >>> backtrack(15, 10, 1, 0, 0)
   (0, 0)
   >>> backtrack(16, 2, 1, 0, 0)
   (0, 1)
   >>> backtrack(20, 1, 1, 0, 0)
   (0, 64)


.. py:function:: solve(needed_sum: int, power: int) -> int

   >>> solve(13, 2)
   1
   >>> solve(10, 2)
   1
   >>> solve(10, 3)
   0
   >>> solve(20, 2)
   1
   >>> solve(15, 10)
   0
   >>> solve(16, 2)
   1
   >>> solve(20, 1)
   Traceback (most recent call last):
       ...
   ValueError: Invalid input
   needed_sum must be between 1 and 1000, power between 2 and 10.
   >>> solve(-10, 5)
   Traceback (most recent call last):
       ...
   ValueError: Invalid input
   needed_sum must be between 1 and 1000, power between 2 and 10.