Skip to main content
Talentd

Ways to Express an Integer as Sum of Powers - Solution & Explanation

MediumDynamic Programming21 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given integers n and x, count how many ways you can represent n as a sum of unique integers where each number is raised to the power x. Each base integer can be used at most once, so the task becomes selecting distinct values i such that i^x adds up exactly to n.

Approach 1: Recursive Search with Memoization (Time: O(n * k), Space: O(n * k))

First compute all possible powers i^x where i^x ≤ n. Let k = floor(n^(1/x)). The recursion explores two choices for each base number: include the current power in the sum or skip it. The recursive state becomes (index, remaining), where index refers to the current base and remaining is the leftover value needed to reach n. Memoization stores results for previously computed states, avoiding repeated exploration of the same subproblems. This turns the exponential brute-force search into a manageable dynamic programming problem and is usually the easiest implementation during interviews. The technique combines recursion with dynamic programming style caching.

Approach 2: Dynamic Programming Table (Time: O(n * k), Space: O(n * k))

This approach converts the recursive decision process into a bottom-up DP table similar to a 0/1 knapsack count problem. Precompute all values i^x up to n. Define dp[i][s] as the number of ways to form sum s using the first i power values. For each power, you either exclude it (dp[i-1][s]) or include it if s ≥ power[i] (dp[i-1][s - power[i]]). Fill the table iteratively until reaching dp[k][n]. This version avoids recursion depth and is easier to reason about for engineers comfortable with classic DP transitions. The structure closely mirrors subset-sum counting.

Recommended for interviews: The memoized recursion is usually the fastest to implement and clearly communicates the include/exclude decision process. Interviewers often expect recognition that the problem reduces to a 0/1 subset-style dynamic programming problem over the values i^x. Showing the recursive solution first demonstrates problem decomposition, while the DP table version demonstrates stronger mastery of bottom-up optimization.

Approach 1: Recursive Approach with Memoization

This approach utilizes recursion to explore all possible combinations of unique integers whose x-th powers sum up to n. To improve its efficiency, we apply memoization to cache the results of state computations and avoid redundant calculations.

We define a recursive function that reduces the target number by the current number raised to the power and recursively calls itself to find valid sequences, caching results along the way for efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the target number. This is due to the number of recursive calls and memoization lookup.

Space Complexity: O(n^2), for the storage used in memoization.

Try this approach in the editor →

Approach 2: Dynamic Programming Table Approach

This approach implements a dynamic programming table to compute the number of ways to represent n using a bottom-up method. By iterating through potential base numbers and powers systematically, it fills a table that records number of valid combinations.

This solution initializes a table `dp` with `dp[0]` set to 1, indicating one way to sum up to zero. Using nested loops, it populates the ways to achieve each sum `j` using integers up to n raised to the power of x.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), iterating through combinations and using nested loops up to n.

Space Complexity: O(n), with an array proportional to n being used.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] as the number of ways to select some numbers from the first i positive integers such that the sum of their x-th powers equals j. Initially, f[0][0] = 1, and all others are 0. The answer is f[n][n].

For each positive integer i, we can choose to either include it or not:

  • Not include it: the number of ways is f[i-1][j];
  • Include it: the number of ways is f[i-1][j-i^x] (provided that j geq i^x).

Therefore, the state transition equation is:

$ f[i][j] = f[i-1][j] + (j geq i^x ? f[i-1][j-i^x] : 0)

Note that the answer can be very large, so we need to take modulo 10^9 + 7.

The time complexity is O(n^2), and the space complexity is O(n^2), where n$ is the given integer in the

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Approach with Memoization

Time Complexity: O(n^2), where n is the target number. This is due to the number of recursive calls and memoization lookup.

Space Complexity: O(n^2), for the storage used in memoization.

Dynamic Programming Table Approach

Time Complexity: O(n^2), iterating through combinations and using nested loops up to n.

Space Complexity: O(n), with an array proportional to n being used.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(n * k)O(n * k)Best for interviews and quick implementation. Clearly models include/exclude decisions.
Dynamic Programming TableO(n * k)O(n * k)Good when recursion depth is undesirable and when converting to classic subset-sum DP.

Video Solution

Ways to Express an Integer as Sum of Powers | Recursion Memo | Leetcode 2787 | codestorywithMIK • codestorywithMIK • 8,824 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Ways to Express an Integer as Sum of Powers easy or hard?
Ways to Express an Integer as Sum of Powers is generally considered a medium difficulty dynamic programming problem. The main challenge is recognizing that distinct powers create a subset-sum counting problem and structuring the recursion or DP transitions correctly.
Ways to Express an Integer as Sum of Powers Python/Java solution
In Python or Java, the typical implementation uses recursion with memoization or a bottom-up DP table. Both approaches iterate over possible powers i^x and update counts for remaining sums until reaching the target n.
How to solve Ways to Express an Integer as Sum of Powers in O(n)?
A strict O(n) solution is not typical for this problem because each possible base power must be considered. The closest efficient solution is O(n * k) dynamic programming, where k = floor(n^(1/x)). The algorithm behaves like a 0/1 subset sum counting problem over values i^x.
What is the best approach for Ways to Express an Integer as Sum of Powers?
The most practical approach is recursive backtracking with memoization. Treat each value i^x as a candidate and decide whether to include or skip it while tracking the remaining sum. Caching states (index, remaining) avoids recomputation and reduces complexity to roughly O(n * k), where k = floor(n^(1/x)).
Is Ways to Express an Integer as Sum of Powers asked at Google/Amazon/Meta?
This problem pattern appears in interviews that test dynamic programming and subset-sum style reasoning. Variations of power-sum or subset counting problems have been reported in interviews at companies like Google, Amazon, and other large tech firms where DP fundamentals are expected.
What data structure is used in Ways to Express an Integer as Sum of Powers?
The solution primarily uses dynamic programming structures such as a 2D DP table or a memoization cache (hash map or array). The algorithm also stores precomputed power values i^x up to n and processes them similarly to a 0/1 knapsack problem.
What is the time complexity of Ways to Express an Integer as Sum of Powers?
The optimized dynamic programming and memoized recursion solutions run in O(n * k) time, where k is the number of valid bases such that i^x ≤ n. Space complexity is also O(n * k) due to memoization or the DP table storing counts for each intermediate sum.

Ready to solve this problem?

Practice Ways to Express an Integer as Sum of Powers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combination Sum IV

Next

Perfect Squares