Ways to Express an Integer as Sum of Powers

medium dynamic programming knapsack subset sum

Problem

Given two positive integers n and x, count the number of ways n can be written as the sum of the x-th power of unique positive integers. That is, count the sets of distinct integers [n₁, …, n_k] with n = n₁^x + … + n_k^x. Because the answer can be large, return it modulo 10⁹ + 7. Constraints: 1 ≤ n ≤ 300, 1 ≤ x ≤ 5.

Inputn = 10, x = 2

Output1

The only way is 10 = 3² + 1². No other distinct squares sum to 10.

n (1–300)

x (1–5)

def numberOfWays(n, x):
    MOD = 10**9 + 7
    # dp[s] = ways to make sum s using x-th powers of distinct bases seen so far
    dp = [0] * (n + 1)
    dp[0] = 1                       # empty set makes sum 0
    base = 1
    while base ** x <= n:           # only bases whose power fits in n
        p = base ** x
        # 0/1 knapsack: walk sums high -> low so each base is used at most once
        for s in range(n, p - 1, -1):
            dp[s] = (dp[s] + dp[s - p]) % MOD
        base += 1
    return dp[n]

function numberOfWays(n, x) {
  const MOD = 1000000007n;
  // dp[s] = ways to make sum s using x-th powers of distinct bases seen so far
  const dp = new Array(n + 1).fill(0n);
  dp[0] = 1n;                       // empty set makes sum 0
  let base = 1;
  while (Math.pow(base, x) <= n) {  // only bases whose power fits in n
    const p = Math.pow(base, x);
    // 0/1 knapsack: walk sums high -> low so each base is used at most once
    for (let s = n; s >= p; s--) {
      dp[s] = (dp[s] + dp[s - p]) % MOD;
    }
    base++;
  }
  return Number(dp[n]);
}

int numberOfWays(int n, int x) {
    final int MOD = 1_000_000_007;
    // dp[s] = ways to make sum s using x-th powers of distinct bases seen so far
    long[] dp = new long[n + 1];
    dp[0] = 1;                       // empty set makes sum 0
    for (int base = 1; Math.pow(base, x) <= n; base++) {
        int p = (int) Math.pow(base, x);
        // 0/1 knapsack: walk sums high -> low so each base is used once
        for (int s = n; s >= p; s--) {
            dp[s] = (dp[s] + dp[s - p]) % MOD;
        }
    }
    return (int) dp[n];
}

int numberOfWays(int n, int x) {
    const long long MOD = 1000000007LL;
    // dp[s] = ways to make sum s using x-th powers of distinct bases seen so far
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;                       // empty set makes sum 0
    for (int base = 1; pow(base, x) <= n; base++) {
        long long p = (long long) pow(base, x);
        // 0/1 knapsack: walk sums high -> low so each base is used once
        for (int s = n; s >= p; s--) {
            dp[s] = (dp[s] + dp[s - p]) % MOD;
        }
    }
    return (int) dp[n];
}

Explanation

Each candidate base contributes its x-th power, and we may take it at most once because the integers must be unique. That is exactly a 0/1 knapsack / subset-sum count: the "items" are the powers 1^x, 2^x, 3^x, … whose value fits within n, and we count how many distinct subsets sum to exactly n.

We keep a one-dimensional table dp where dp[s] is the number of ways to reach sum s using the bases processed so far. We start with dp[0] = 1 (the empty set sums to 0) and all other entries 0.

For each base b with p = b^x ≤ n, we fold its power into the table. The key detail is the direction of the inner loop: we update sums from high to low (s = n … p). Going downward guarantees that dp[s - p] still reflects subsets that have not yet used base b, so each base is counted only once. Iterating upward would let a base be reused and would solve the unbounded-coins variant instead.

The recurrence is dp[s] += dp[s - p]: every subset summing to s - p can be extended with base b to reach s. We take the result modulo 10⁹ + 7 to keep numbers small.

Example: n = 10, x = 2. The usable powers are 1, 4, 9 (since 16 > 10). After folding all three, dp[10] equals 1, matching the unique decomposition 10 = 9 + 1 = 3² + 1².

Time: O(n · n^1/x) Space: O(n)