Ways to express an integer as sum of powers

Dynamic Programming

49.9% acceptance

Feb 25, 2026

844

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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 dp = vec![0i64; n + 1];
    dp[0] = 1;
    let mut k = 1usize;
    // 0/1 knapsack: each k can be used at most once
    while k.pow(x) <= n {
      let kx = k.pow(x);
      for j in (kx..=n).rev() {
        dp[j] = (dp[j] + dp[j - kx]) % MOD;
      }
      k += 1;
    }
    dp[n] as i32
  }
}