Problem

Given two positive integers n and x.

Return the number of waysn can be expressed as the sum of thexth _power ofunique positive integers, in other words, the number of sets of unique integers _[n1, n2, ..., nk]wheren = n1x + n2x + ... + nkx .

Since the result can be very large, return it modulo 10^9 + 7.

For example, if n = 160 and x = 3, one way to express n is `n = 23 + 33

  • 53`.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5

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 <= 300
  • 1 <= x <= 5

Solution

Method 1 – DP (Knapsack with Unique Elements)

Intuition

This is a variation of the subset sum problem, where each number can be used at most once, and the numbers are their x-th powers. We use dynamic programming to count the number of ways to sum to n using unique powers.

Approach

  1. Precompute all possible k^x ≤ n.
  2. Use a DP array where dp[i] is the number of ways to sum to i.
  3. For each power, update dp from n down to power (to ensure uniqueness).
  4. Return dp[n].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int numberOfWays(int n, int x) {
        const int MOD = 1e9+7;
        vector<int> pows;
        for (int k = 1; ; ++k) {
            int v = pow(k, x);
            if (v > n) break;
            pows.push_back(v);
        }
        vector<int> dp(n+1);
        dp[0] = 1;
        for (int v : pows) {
            for (int i = n; i >= v; --i) {
                dp[i] = (dp[i] + dp[i-v]) % MOD;
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func numberOfWays(n int, x int) int {
    const mod = 1_000_000_007
    pows := []int{}
    for k := 1; ; k++ {
        v := 1
        for i := 0; i < x; i++ {
            v *= k
        }
        if v > n {
            break
        }
        pows = append(pows, v)
    }
    dp := make([]int, n+1)
    dp[0] = 1
    for _, v := range pows {
        for i := n; i >= v; i-- {
            dp[i] = (dp[i] + dp[i-v]) % mod
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
class Solution {
    public int numberOfWays(int n, int x) {
        int mod = 1_000_000_007;
        List<Integer> pows = new ArrayList<>();
        for (int k = 1; ; k++) {
            int v = (int)Math.pow(k, x);
            if (v > n) break;
            pows.add(v);
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int v : pows) {
            for (int i = n; i >= v; i--) {
                dp[i] = (dp[i] + dp[i-v]) % mod;
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun numberOfWays(n: Int, x: Int): Int {
        val mod = 1_000_000_007
        val pows = mutableListOf<Int>()
        var k = 1
        while (true) {
            val v = Math.pow(k.toDouble(), x.toDouble()).toInt()
            if (v > n) break
            pows.add(v)
            k++
        }
        val dp = IntArray(n+1)
        dp[0] = 1
        for (v in pows) {
            for (i in n downTo v) {
                dp[i] = (dp[i] + dp[i-v]) % mod
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        pows = []
        k = 1
        while True:
            v = k ** x
            if v > n:
                break
            pows.append(v)
            k += 1
        dp = [0] * (n+1)
        dp[0] = 1
        for v in pows:
            for i in range(n, v-1, -1):
                dp[i] = (dp[i] + dp[i-v]) % MOD
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn number_of_ways(n: i32, x: i32) -> i32 {
        let m = 1_000_000_007;
        let mut pows = vec![];
        let mut k = 1;
        while k.pow(x as u32) <= n {
            pows.push(k.pow(x as u32));
            k += 1;
        }
        let n = n as usize;
        let mut dp = vec![0; n+1];
        dp[0] = 1;
        for &v in &pows {
            let v = v as usize;
            for i in (v..=n).rev() {
                dp[i] = (dp[i] + dp[i-v]) % m;
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    numberOfWays(n: number, x: number): number {
        const mod = 1_000_000_007;
        const pows: number[] = [];
        let k = 1;
        while (true) {
            const v = Math.pow(k, x);
            if (v > n) break;
            pows.push(v);
            k++;
        }
        const dp = new Array(n+1).fill(0);
        dp[0] = 1;
        for (const v of pows) {
            for (let i = n; i >= v; i--) {
                dp[i] = (dp[i] + dp[i-v]) % mod;
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n * sqrt(n)) — For each power ≤ n, we update the dp array up to n. The number of powers is O(n^{1/x}).
  • 🧺 Space complexity: O(n) — For the dp array.