<p>Given two <strong>positive</strong> integers <code>n</code> and <code>x</code>.</p>

<p>Return <em>the number of ways </em><code>n</code><em> can be expressed as the sum of the </em><code>x<sup>th</sup></code><em> power of <strong>unique</strong> positive integers, in other words, the number of sets of unique integers </em><code>[n<sub>1</sub>, n<sub>2</sub>, ..., n<sub>k</sub>]</code><em> where </em><code>n = n<sub>1</sub><sup>x</sup> + n<sub>2</sub><sup>x</sup> + ... + n<sub>k</sub><sup>x</sup></code><em>.</em></p>

<p>Since the result can be very large, return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>For example, if <code>n = 160</code> and <code>x = 3</code>, one way to express <code>n</code> is <code>n = 2<sup>3</sup> + 3<sup>3</sup> + 5<sup>3</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10, x = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can express n as the following: n = 3<sup>2</sup> + 1<sup>2</sup> = 10.
It can be shown that it is the only way to express 10 as the sum of the 2<sup>nd</sup> power of unique integers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4, x = 1
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can express n in the following ways:
- n = 4<sup>1</sup> = 4.
- n = 3<sup>1</sup> + 1<sup>1</sup> = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>1 &lt;= x &lt;= 5</code></li>
</ul>

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        """
        - If n is between 1 and three hundred, could pretty easily find all a's such that a^x
          is less than n
        - Then could do either a cached DFS to count combinations, some kind of bottoms-up DP

        Top-down: O(n * n**1/x) CC | O(n * n**1/x) MC
        - Init units = []
        - Iterate from 1->n, as a until a^x > n, adding a^x to units
        - Init a cache in the form of sum: count of combos to get there
        - Create a backtrack helper, taking units_index, curr_sum
            - if curr_sum == n, return 1
            - if curr_sum > n, return 0
            - if curr_sum is in cache, return cache[curr_sum]
            - cache[curr_sum] = backtrack
            - iterate from i to len(units):
                - add i to curr_sum
                - cache[curr_sum] += backtrack
                - remove i from curr_sum
            - return cache[curr_sum]

        Bottoms up:
        - Init units = []
        - Iterate from 1->n, as a until a^x > n, adding a^x to units
        - Init dp nested array where every column is the number of paths to that sum
          and each row corresponds to a unit
        """
        units = self.build_units(n, x)
        dp = [[0] * (n+1) for _ in range(len(units) + 1)]
        for row in dp:
            row[0] = 1

        for i in range(1, len(units) + 1):
            unit = units[i-1]
            # print("unit", unit)
            for partial, count in enumerate(dp[i - 1]):
                dp[i][partial] = max(count, dp[i][partial])

                if partial + unit <= n:
                    # print("less equal")
                    dp[i][partial + unit] = (dp[i-1][partial + unit] + count)

           
            # print(dp)

        return int(dp[-1][n] % (10**9 + 7))
    
    def build_units(self, n: int, x: int):
        units = []
        for i in range(1, n + 1):
            if i**x > n:
                break
            units.append(i**x)

        return units
1520