Given two positive integers n and x.
Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1x + n2x + ... + nkx.
Since the result can be very large, return it modulo 109 + 7.
For example, if n = 160 and x = 3, one way to express n is n = 23 + 33 + 53.
Example 1:
Input: n = 10, x = 2 Output: 1 Explanation: We can express n as the following: n = 32 + 12 = 10. It can be shown that it is the only way to express 10 as the sum of the 2nd power of unique integers.
Example 2:
Input: n = 4, x = 1 Output: 2 Explanation: We can express n in the following ways: - n = 41 = 4. - n = 31 + 11 = 4.
Constraints:
1 <= n <= 3001 <= x <= 5Problem Overview: Given integers n and x, count how many ways you can represent n as a sum of unique integers where each number is raised to the power x. Each base integer can be used at most once, so the task becomes selecting distinct values i such that i^x adds up exactly to n.
Approach 1: Recursive Search with Memoization (Time: O(n * k), Space: O(n * k))
First compute all possible powers i^x where i^x ≤ n. Let k = floor(n^(1/x)). The recursion explores two choices for each base number: include the current power in the sum or skip it. The recursive state becomes (index, remaining), where index refers to the current base and remaining is the leftover value needed to reach n. Memoization stores results for previously computed states, avoiding repeated exploration of the same subproblems. This turns the exponential brute-force search into a manageable dynamic programming problem and is usually the easiest implementation during interviews. The technique combines recursion with dynamic programming style caching.
Approach 2: Dynamic Programming Table (Time: O(n * k), Space: O(n * k))
This approach converts the recursive decision process into a bottom-up DP table similar to a 0/1 knapsack count problem. Precompute all values i^x up to n. Define dp[i][s] as the number of ways to form sum s using the first i power values. For each power, you either exclude it (dp[i-1][s]) or include it if s ≥ power[i] (dp[i-1][s - power[i]]). Fill the table iteratively until reaching dp[k][n]. This version avoids recursion depth and is easier to reason about for engineers comfortable with classic DP transitions. The structure closely mirrors subset-sum counting.
Recommended for interviews: The memoized recursion is usually the fastest to implement and clearly communicates the include/exclude decision process. Interviewers often expect recognition that the problem reduces to a 0/1 subset-style dynamic programming problem over the values i^x. Showing the recursive solution first demonstrates problem decomposition, while the DP table version demonstrates stronger mastery of bottom-up optimization.
This approach utilizes recursion to explore all possible combinations of unique integers whose x-th powers sum up to n. To improve its efficiency, we apply memoization to cache the results of state computations and avoid redundant calculations.
We define a recursive function that reduces the target number by the current number raised to the power and recursively calls itself to find valid sequences, caching results along the way for efficiency.
Time Complexity: O(n^2), where n is the target number. This is due to the number of recursive calls and memoization lookup.
Space Complexity: O(n^2), for the storage used in memoization.
This approach implements a dynamic programming table to compute the number of ways to represent n using a bottom-up method. By iterating through potential base numbers and powers systematically, it fills a table that records number of valid combinations.
This solution initializes a table `dp` with `dp[0]` set to 1, indicating one way to sum up to zero. Using nested loops, it populates the ways to achieve each sum `j` using integers up to n raised to the power of x.
Time Complexity: O(n^2), iterating through combinations and using nested loops up to n.
Space Complexity: O(n), with an array proportional to n being used.
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(n^2), where n is the target number. This is due to the number of recursive calls and memoization lookup. Space Complexity: O(n^2), for the storage used in memoization. |
| Dynamic Programming Table Approach | Time Complexity: O(n^2), iterating through combinations and using nested loops up to n. Space Complexity: O(n), with an array proportional to n being used. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n * k) | O(n * k) | Best for interviews and quick implementation. Clearly models include/exclude decisions. |
| Dynamic Programming Table | O(n * k) | O(n * k) | Good when recursion depth is undesirable and when converting to classic subset-sum DP. |
Ways to Express an Integer as Sum of Powers | Recursion Memo | Leetcode 2787 | codestorywithMIK • codestorywithMIK • 8,613 views views
Watch 9 more video solutions →Practice Ways to Express an Integer as Sum of Powers with our built-in code editor and test cases.
Practice on FleetCode