Watch 10 video solutions for Ways to Express an Integer as Sum of Powers, a medium level problem involving Dynamic Programming. This walkthrough by codestorywithMIK has 8,613 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |