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 <= 5The key idea in #2787 Ways to Express an Integer as Sum of Powers is to count how many unique combinations of integers raised to a power x can sum up to a target n. First, generate all possible values of the form i^x such that they are less than or equal to n. The problem then becomes similar to a subset sum / 0-1 knapsack counting problem.
Using dynamic programming, maintain a DP array where dp[s] represents the number of ways to reach sum s using the generated powers. Iterate through each power and update the DP states in reverse to ensure each value is used at most once. This approach efficiently counts valid combinations while avoiding duplicates.
The number of candidate powers is limited by n^(1/x), making the DP feasible for typical constraints. The overall time complexity is roughly O(k * n), where k is the number of valid powers, and the space complexity is O(n).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Subset Sum style) | O(k * n) where k ≈ n^(1/x) | O(n) |
| DFS + Memoization | O(k * n) in typical cases | O(k * n) memo storage |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
You can use dynamic programming, where dp[k][j] represents the number of ways to express k as the sum of the x-th power of unique positive integers such that the biggest possible number we use is j.
To calculate dp[k][j], you can iterate over the numbers smaller than j and try to use each one as a power of x to make our sum k.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Each integer power can either be chosen or skipped, and each can only be used once. This decision process mirrors the subset sum or 0-1 knapsack pattern where we count ways to reach a target sum.
While the exact problem may not always appear, its underlying concepts are common in technical interviews. Companies often test variations of subset sum, combinatorial counting, and dynamic programming problems.
A dynamic programming array is the most effective structure for this problem. It tracks how many ways each intermediate sum can be formed, similar to the classic 0-1 knapsack or subset sum pattern.
The optimal approach typically uses dynamic programming. After generating all integers raised to power x that are less than or equal to n, the problem becomes a subset-sum counting task where each value can be used at most once.