Move from brute-force thinking to an efficient approach using dynamic programming strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
10 2
4 1
perfect-squares)combination-sum-iv)target-sum)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2787: Ways to Express an Integer as Sum of Powers
class Solution {
public int numberOfWays(int n, int x) {
final int mod = (int) 1e9 + 7;
int[][] f = new int[n + 1][n + 1];
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
long k = (long) Math.pow(i, x);
for (int j = 0; j <= n; ++j) {
f[i][j] = f[i - 1][j];
if (k <= j) {
f[i][j] = (f[i][j] + f[i - 1][j - (int) k]) % mod;
}
}
}
return f[n][n];
}
}
// Accepted solution for LeetCode #2787: Ways to Express an Integer as Sum of Powers
func numberOfWays(n int, x int) int {
const mod int = 1e9 + 7
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, n+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
k := int(math.Pow(float64(i), float64(x)))
for j := 0; j <= n; j++ {
f[i][j] = f[i-1][j]
if k <= j {
f[i][j] = (f[i][j] + f[i-1][j-k]) % mod
}
}
}
return f[n][n]
}
# Accepted solution for LeetCode #2787: Ways to Express an Integer as Sum of Powers
class Solution:
def numberOfWays(self, n: int, x: int) -> int:
mod = 10**9 + 7
f = [[0] * (n + 1) for _ in range(n + 1)]
f[0][0] = 1
for i in range(1, n + 1):
k = pow(i, x)
for j in range(n + 1):
f[i][j] = f[i - 1][j]
if k <= j:
f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod
return f[n][n]
// Accepted solution for LeetCode #2787: Ways to Express an Integer as Sum of Powers
impl Solution {
pub fn number_of_ways(n: i32, x: i32) -> i32 {
const MOD: i64 = 1_000_000_007;
let n = n as usize;
let x = x as u32;
let mut f = vec![vec![0; n + 1]; n + 1];
f[0][0] = 1;
for i in 1..=n {
let k = (i as i64).pow(x);
for j in 0..=n {
f[i][j] = f[i - 1][j];
if j >= k as usize {
f[i][j] = (f[i][j] + f[i - 1][j - k as usize]) % MOD;
}
}
}
f[n][n] as i32
}
}
// Accepted solution for LeetCode #2787: Ways to Express an Integer as Sum of Powers
function numberOfWays(n: number, x: number): number {
const mod = 10 ** 9 + 7;
const f = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
const k = Math.pow(i, x);
for (let j = 0; j <= n; ++j) {
f[i][j] = f[i - 1][j];
if (k <= j) {
f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
}
}
}
return f[n][n];
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.