LeetCode 2787 - Ways to Express an Integer as Sum of Powers

LeetCode Problem 2787

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

This problem asks us to count how many different ways we can represent a given integer n as the sum of distinct positive integers raised to the power x.

More formally, we want to find the number of unique sets:

$$[n_1, n_2, ..., n_k]$$

such that:

$$n = n_1^x + n_2^x + \dots + n_k^x$$

The important restriction is that all integers must be unique. This means we cannot reuse the same number multiple times. For example, if x = 2, then using 1² + 1² + 2² is invalid because 1 appears twice.

The input consists of two integers:

• n, the target sum we want to form
• x, the exponent applied to each chosen integer

The output is the total number of valid combinations modulo:

$$10^9 + 7$$

The modulo is necessary because the number of possible combinations may become large.

The constraints are relatively small:

• 1 <= n <= 300
• 1 <= x <= 5

These limits strongly suggest that a dynamic programming solution is feasible. Since n is at most 300, we can afford algorithms with time complexity around O(n²).

A key observation is that the number of candidate integers is also small. For any integer k, we only care about values where:

$$k^x \le n$$

For example, if n = 300 and x = 5, only a few numbers satisfy this condition.

There are several important edge cases to consider:

• When x = 1, the problem becomes counting subsets of distinct integers whose sum equals n
• When n itself is a perfect xth power, there is always at least one solution consisting of a single number
• Some values of n may have no valid representation at all
• Because uniqueness is required, this is a 0/1 selection problem rather than an unbounded knapsack problem

Understanding the uniqueness constraint is critical because it determines how the dynamic programming transition must be performed.

Approaches

Brute Force Approach

A straightforward solution is to generate every possible subset of integers whose xth powers do not exceed n.

For example, if n = 10 and x = 2, the candidate powers are:

$$1^2 = 1,\quad 2^2 = 4,\quad 3^2 = 9$$

We could recursively decide for each candidate whether to include it or not.

At each step:

• Include the current power
• Exclude the current power

Whenever the running sum becomes exactly n, we count one valid way.

This brute-force approach is correct because it explores every possible subset exactly once. Since every valid representation corresponds to a unique subset of powers, the algorithm eventually finds all valid solutions.

However, the time complexity is exponential because each candidate introduces two choices. If there are m candidate powers, the complexity becomes:

$$O(2^m)$$

Although the constraints are small, exponential recursion is still inefficient and unnecessary.

Key Insight

This problem is fundamentally a subset-sum counting problem.

Each integer power can either:

• Be used once
• Not be used

That is exactly the behavior of a 0/1 knapsack dynamic programming problem.

Instead of recursively exploring all subsets, we can build solutions incrementally using dynamic programming.

We first compute all valid powers:

$$1^x, 2^x, 3^x, \dots$$

up to n.

Then we define:

$$dp[s]$$

as the number of ways to form sum s.

Initially:

$$dp[0] = 1$$

because there is exactly one way to make sum 0, choose nothing.

For each power value p, we update the DP array in reverse order:

$$dp[s] += dp[s - p]$$

The reverse iteration is essential because it guarantees each power is used at most once.

This transforms the exponential search into a polynomial-time dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m)	O(m)	Recursively explores every subset of candidate powers
Optimal Dynamic Programming	O(m × n)	O(n)	Uses 0/1 knapsack style DP to count valid subsets efficiently

Here, m is the number of integers whose xth power is at most n.

Algorithm Walkthrough

1. Generate all candidate powers.

Start with integer 1 and repeatedly compute:

$$k^x$$

Continue while the value is less than or equal to n.

These are the only numbers that can possibly participate in a valid sum. 2. Create a DP array.

Define:

dp[s] = number of ways to form sum s

Initialize the array with zeros and set:

dp[0] = 1

This represents the empty subset. 3. Process each power one by one.

For each power value p, update the DP array from right to left.

Reverse iteration is important because it prevents reusing the same power multiple times. 4. Update reachable sums.

For every sum s from n down to p:

dp[s] += dp[s - p]

This means:

• Existing ways to form s remain valid
• Every way to form s - p can now form s by adding power p

5. Apply modulo arithmetic.

Since counts may become large, take modulo:

$$10^9 + 7$$

after every update. 6. Return the final answer.

After processing all powers, dp[n] contains the total number of valid representations.

Why it works

The algorithm works because each candidate power is processed exactly once, and reverse iteration guarantees that each power contributes at most once to any sum.

The DP invariant is:

$$dp[s]$$

always represents the number of ways to form sum s using only the powers processed so far.

Since every subset of powers is considered exactly once, the final value dp[n] equals the number of valid unique representations.

Python Solution

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7

        powers = []
        num = 1

        while (value := num ** x) <= n:
            powers.append(value)
            num += 1

        dp = [0] * (n + 1)
        dp[0] = 1

        for power in powers:
            for current_sum in range(n, power - 1, -1):
                dp[current_sum] = (
                    dp[current_sum] + dp[current_sum - power]
                ) % MOD

        return dp[n]

The implementation begins by generating every valid xth power that does not exceed n. These values form the set of usable numbers in the subset-sum problem.

The dp array stores the number of ways to create each sum from 0 to n. The initialization:

dp[0] = 1

represents the empty subset.

The outer loop iterates through each power exactly once. The inner loop iterates backward from n down to the current power. This backward traversal is the standard technique used in 0/1 knapsack problems to prevent reusing the same element multiple times.

For each state transition:

dp[current_sum] += dp[current_sum - power]

we extend all existing ways to form current_sum - power by including the current power.

Finally, dp[n] contains the total number of valid representations.

Go Solution

package main

func numberOfWays(n int, x int) int {
	const MOD int = 1_000_000_007

	powers := []int{}

	for num := 1; ; num++ {
		value := 1

		for i := 0; i < x; i++ {
			value *= num
		}

		if value > n {
			break
		}

		powers = append(powers, value)
	}

	dp := make([]int, n+1)
	dp[0] = 1

	for _, power := range powers {
		for currentSum := n; currentSum >= power; currentSum-- {
			dp[currentSum] =
				(dp[currentSum] + dp[currentSum-power]) % MOD
		}
	}

	return dp[n]
}

The Go implementation follows the same dynamic programming strategy as the Python version.

One small difference is that Go does not have a built-in exponentiation operator for integers, so powers are computed manually using repeated multiplication.

The DP slice is initialized with length n + 1, and reverse iteration is used exactly as in the Python solution to enforce uniqueness of selected integers.

Because Go integers are sufficiently large for this problem's constraints, overflow is not an issue before modulo reduction.

Worked Examples

Example 1

Input: n = 10, x = 2

First compute all square numbers less than or equal to 10.

Integer	Power
1	1
2	4
3	9

So:

powers = [1, 4, 9]

Initialize DP:

Sum	dp
0	1
1-10	0

Initial state:

Sum	0	1	2	3	4	5	6	7	8	9	10
dp	1	0	0	0	0	0	0	0	0	0	0

Process power 1.

Update sums from 10 down to 1.

Result:

Sum	0	1	2	3	4	5	6	7	8	9	10
dp	1	1	0	0	0	0	0	0	0	0	0

Process power 4.

Sum	0	1	2	3	4	5	6	7	8	9	10
dp	1	1	0	0	1	1	0	0	0	0	0

Now:

• 4 can be formed directly
• 5 can be formed as 1 + 4

Process power 9.

Sum	0	1	2	3	4	5	6	7	8	9	10
dp	1	1	0	0	1	1	0	0	0	1	1

Finally:

dp[10] = 1

The only valid representation is:

$$10 = 1^2 + 3^2$$

Example 2

Input: n = 4, x = 1

Candidate powers:

[1, 2, 3, 4]

Initial DP:

Sum	0	1	2	3	4
dp	1	0	0	0	0

After processing 1:

Sum	0	1	2	3	4
dp	1	1	0	0	0

After processing 2:

Sum	0	1	2	3	4
dp	1	1	1	1	0

After processing 3:

Sum	0	1	2	3	4
dp	1	1	1	2	1

After processing 4:

Sum	0	1	2	3	4
dp	1	1	1	2	2

Thus:

dp[4] = 2

The two valid representations are:

$$4$$

and

$$3 + 1$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	For each candidate power, iterate through all sums up to n
Space	O(n)	Only a one-dimensional DP array is stored

Here, m is the number of integers satisfying:

$$k^x \le n$$

Since n <= 300, m is small, making the algorithm very efficient.

The reverse iteration allows us to reuse a single DP array instead of requiring a full two-dimensional table.

Test Cases

sol = Solution()

assert sol.numberOfWays(10, 2) == 1  # Example 1
assert sol.numberOfWays(4, 1) == 2  # Example 2

assert sol.numberOfWays(1, 1) == 1  # Single number itself
assert sol.numberOfWays(1, 5) == 1  # 1^5 = 1

assert sol.numberOfWays(2, 2) == 0  # No way to express 2 as unique squares
assert sol.numberOfWays(3, 2) == 0  # No valid square decomposition

assert sol.numberOfWays(5, 2) == 1  # 1^2 + 2^2
assert sol.numberOfWays(9, 2) == 1  # 3^2 only

assert sol.numberOfWays(100, 2) > 0  # Larger input with multiple solutions
assert sol.numberOfWays(300, 1) > 0  # Maximum n with many combinations

assert sol.numberOfWays(17, 2) == 1  # 1^2 + 4^2
assert sol.numberOfWays(160, 3) == 1  # Example from statement: 2^3 + 3^3 + 5^3

Test Summary

Test	Why
(10, 2)	Verifies standard square decomposition
(4, 1)	Verifies subset-sum behavior
(1, 1)	Smallest possible input
(1, 5)	High exponent edge case
(2, 2)	No valid representation
(3, 2)	Another impossible case
(5, 2)	Simple valid square sum
(9, 2)	Perfect square single-element solution
(100, 2)	Larger input with many combinations
(300, 1)	Stress test near maximum constraints
(17, 2)	Combination of multiple squares
(160, 3)	Cubic powers example

Edge Cases

One important edge case occurs when n itself is a perfect xth power. For example:

$$n = 9,\quad x = 2$$

In this situation, there is always at least one valid solution consisting of a single integer. Some implementations accidentally overlook single-element subsets while focusing on combinations. The DP solution handles this naturally because each power directly updates its own index.

Another critical edge case occurs when no valid representation exists. For example:

$$n = 2,\quad x = 2$$

The only square less than or equal to 2 is 1, but uniqueness prevents using 1 twice. Incorrect implementations that allow repeated usage would incorrectly count:

$$1^2 + 1^2$$

The reverse DP iteration prevents this bug by ensuring every power is used at most once.

A third important edge case appears when x = 1. In that case, every positive integer up to n becomes a candidate:

$$1, 2, 3, \dots, n$$

This produces the largest number of possible combinations and stresses the dynamic programming transitions. The algorithm still works efficiently because the total complexity remains bounded by:

$$O(n^2)$$

which is entirely manageable for n <= 300.