# Ways to Express an Integer as Sum of Powers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ways-to-express-an-integer-as-sum-of-powers)
Canonical: https://scaleengineer.com/dsa/problems/ways-to-express-an-integer-as-sum-of-powers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
---
## Problem
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`

# Approaches
## Brute-force Recursion (Backtracking)
This approach uses a simple recursive function to explore all possible combinations of unique integer powers that could sum up to `n`. It tries including or excluding each possible power `num^x` and recursively calls itself for the remaining target sum. This method directly translates the problem's combinatorial nature into code but without any optimizations.
**Time:** O(2^k), where `k` is the number of candidate integers (`k <= n^(1/x)`). This is exponential and too slow for the given constraints. · **Space:** O(k), where `k` is the maximum possible base number such that `k^x <= n`. This space is used by the recursion stack. In the worst case (`x=1`), this is O(n).
**Pros:** Simple to understand and implement.; Follows the problem definition very closely.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
We define a recursive helper function, say `countWays(target, num)`, where `target` is the remaining sum we need to achieve, and `num` is the current integer base we are considering. The function explores two possibilities for each `num`:

1.  **Include `num^x`**: If we use `num^x`, the new target becomes `target - num^x`, and we move to the next integer `num + 1` to ensure uniqueness.
2.  **Exclude `num^x`**: If we don't use `num^x`, the target remains the same, and we move to `num + 1`.

The total number of ways is the sum of ways from these two choices. The recursion stops when a solution is found (`target == 0`), or when a path becomes invalid (`target < 0` or `num^x > target`). The initial call is `countWays(n, 1)`.

```java
class Solution {
    int MOD = 1_000_000_007;

    public int numberOfWays(int n, int x) {
        return countWays(n, 1, x);
    }

    private int countWays(int target, int num, int x) {
        // Base case: A valid combination is found.
        if (target == 0) {
            return 1;
        }

        long power = 1;
        for (int i = 0; i < x; i++) power *= num;

        // Base case: Current number's power exceeds target, or target becomes negative.
        if (target < 0 || power > target) {
            return 0;
        }

        // Recursive step:
        // 1. Include the current number's power.
        int waysWith = countWays(target - (int) power, num + 1, x);
        
        // 2. Exclude the current number's power.
        int waysWithout = countWays(target, num + 1, x);

        return (waysWith + waysWithout) % MOD;
    }
}
```
### Algorithm
- Define a recursive function `countWays(target, num, x)`.
- **Base Case 1**: If `target` is 0, a valid combination is found. Return 1.
- **Base Case 2**: If `target` is negative, or if `num^x` is greater than `target`, this path is invalid. Return 0.
- **Recursive Step**: Explore two choices for the current number `num`:
  - **Include `num^x`**: Recursively call `countWays(target - num^x, num + 1, x)`.
  - **Exclude `num^x`**: Recursively call `countWays(target, num + 1, x)`.
- The result is the sum of the outcomes of these two choices, taken modulo `10^9 + 7`.
- The initial call is `countWays(n, 1, x)`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by using memoization to store the results of subproblems. By caching the results in a 2D array, we avoid re-calculating the number of ways for a given `(target, num)` state. This is a top-down dynamic programming approach that significantly improves performance.
**Time:** O(n * k), where `k` is the number of candidate integers (`k <= n^(1/x)`). Each state `(target, num)` is computed only once. · **Space:** O(n * k), where `k <= n^(1/x)`. This is for the memoization table. The recursion stack adds an additional O(k) space.
**Pros:** Drastically reduces time complexity compared to brute-force, making it efficient enough for the given constraints.; Maintains a logical structure that is similar to the pure recursive solution.
**Cons:** Uses more space than the iterative bottom-up DP approach due to the 2D memoization table and the recursion stack.; Can lead to a stack overflow error for very deep recursion, though not an issue with the given constraints.
### Explanation
This approach enhances the brute-force recursion by adding a memoization table (a 2D array `dp`) to store the results of subproblems. This technique is also known as top-down dynamic programming. The state is defined by `(target, num)`, so `dp[target][num]` stores the result for `countWays(target, num)`. Before any computation, the function checks the `dp` table. If a result exists, it's returned immediately. Otherwise, the result is computed, stored in the table, and then returned. This prevents re-computation of the same state, drastically improving efficiency.

```java
class Solution {
    int MOD = 1_000_000_007;
    Integer[][] dp;

    public int numberOfWays(int n, int x) {
        // dp[i][j] will store the number of ways to get sum 'i' using numbers from 'j' onwards.
        dp = new Integer[n + 1][n + 1];
        return solve(n, 1, x);
    }

    private int solve(int target, int num, int x) {
        if (target == 0) {
            return 1;
        }
        
        long power = power(num, x);
        if (num > n || target < 0 || power > target) {
            return 0;
        }

        if (dp[target][num] != null) {
            return dp[target][num];
        }

        // Option 1: Include num^x
        int include = solve(target - (int)power, num + 1, x);
        
        // Option 2: Exclude num^x
        int exclude = solve(target, num + 1, x);

        dp[target][num] = (include + exclude) % MOD;
        return dp[target][num];
    }

    // Custom power function to avoid double precision issues and handle overflow
    private long power(int base, int exp) {
        long res = 1;
        for (int i = 0; i < exp; i++) {
            res *= base;
            if (res > 301) return 301; // Cap at n+1, since n <= 300
        }
        return res;
    }
}
```
### Algorithm
- Create a memoization table `dp[n+1][k+1]` initialized with a sentinel value (e.g., `null` or -1), where `k` is the max base.
- Define a recursive function `solve(target, num, x)`.
- **Base Cases**: Same as the brute-force approach.
- **Memoization Check**: Before computing, check if `dp[target][num]` has been calculated. If so, return the stored value.
- **Recursive Step**: If not memoized, compute the result by summing the 'include' and 'exclude' options as in the brute-force approach.
- **Store Result**: Store the computed result in `dp[target][num]` before returning.
- The initial call is `solve(n, 1, x)`.

## Iterative Dynamic Programming (Bottom-Up DP)
This is a bottom-up dynamic programming approach that iteratively builds the solution. It's analogous to the 0/1 Knapsack problem and is generally the most efficient method in terms of both time and space. We use a 1D array to keep track of the number of ways to form each sum from 0 to `n`.
**Time:** O(n * k), where `k` is the number of candidate integers (`k <= n^(1/x)`). This is asymptotically the same as the memoized approach. · **Space:** O(n), for the 1D DP array. This is the most space-efficient approach.
**Pros:** Most efficient in terms of space complexity.; Avoids recursion overhead, which can lead to slightly better constant-factor performance than the memoized version.; Iterative nature prevents any risk of stack overflow.
**Cons:** The logic, especially the downward iteration for the inner loop, can be less intuitive to grasp compared to the recursive formulation.
### Explanation
This approach uses bottom-up dynamic programming, which is an iterative way to solve the problem. It's conceptually similar to the 0/1 Knapsack problem. We use a 1D array `dp` of size `n+1`, where `dp[i]` stores the number of ways to form the sum `i`. We initialize `dp[0] = 1` (one way to make a sum of 0: using no numbers). Then, we iterate through each possible number we can use, which are `1^x, 2^x, 3^x, ...` as long as the power is less than or equal to `n`. For each power `p = num^x`, we update the `dp` array. We iterate from `j = n` down to `p`. The update rule is `dp[j] = (dp[j] + dp[j - p])`. The downward loop for `j` is critical; it ensures that each power `p` is used at most once in any given sum, fulfilling the 'unique integers' requirement. The final answer is `dp[n]`.

```java
class Solution {
    public int numberOfWays(int n, int x) {
        int MOD = 1_000_000_007;
        int[] dp = new int[n + 1];
        dp[0] = 1;

        // Iterate through each number 'num' whose x-th power could be part of the sum.
        for (int num = 1; ; num++) {
            long powerVal = 1;
            // Calculate num^x safely, checking for overflow against n.
            for (int i = 0; i < x; i++) {
                powerVal *= num;
                if (powerVal > n) break;
            }
            
            if (powerVal > n) {
                break; // All subsequent numbers will also have powers > n.
            }

            int power = (int) powerVal;

            // Iterate downwards to ensure each number's power is used at most once (0/1 knapsack style).
            for (int j = n; j >= power; j--) {
                dp[j] = (dp[j] + dp[j - power]) % MOD;
            }
        }

        return dp[n];
    }
}
```
### Algorithm
- Create a 1D DP array `dp` of size `n + 1` and initialize all elements to 0.
- Set `dp[0] = 1`, as there is one way to make a sum of 0 (by choosing no numbers).
- Iterate through each possible base number `num` from 1 upwards.
- For each `num`, calculate its power `p = num^x`. If `p > n`, stop.
- For each `p`, iterate `j` from `n` down to `p`.
- Update `dp[j]` using the formula: `dp[j] = (dp[j] + dp[j - p]) % MOD`.
- The downward iteration of `j` ensures that each power `p` is used at most once for any sum.
- The final answer is `dp[n]`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfWays(int n, int x) {
    final int mod = (int)1 e9 + 7;
    int[][] f = new int[n + 1][n + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      long k = (long)Math.pow(i, x);
      for (int j = 0; j <= n; ++j) {
        f[i][j] = f[i - 1][j];
        if (k <= j) {
          f[i][j] = (f[i][j] + f[i - 1][j - (int)k]) % mod;
        }
      }
    }
    return f[n][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfWays(int n, int x) {
    const int mod = 1e9 + 7;
    int f[n + 1][n + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      long long k = (long long)pow(i, x);
      for (int j = 0; j <= n; ++j) {
        f[i][j] = f[i - 1][j];
        if (k <= j) {
          f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
        }
      }
    }
    return f[n][n];
  }
};

```

### Python

```python
class Solution:
    def numberOfWays(self, n: int, x: int) -> int: mod = 10 ** 9 + 7 f = [[0] * (n + 1) for _ in range(n + 1)] f[0][0] = 1 for i in range(1, n + 1): k = pow(i, x) for j in range(n + 1): f[i][j] = f[i - 1][j] if k <= j: f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod return f[n][n]

```