2787. Ways to Express an Integer as Sum of Powers

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.

class Solution {
    long long dp[333][333], mod = 1e9 + 7;
    long long helper(int n, int lim) {
        if(n < 0) return 0;
        if(n == 0) return 1;
        if(dp[n][lim] != -1) return dp[n][lim];
        long long& res = dp[n][lim] = 0;
        for(int i = 1; i <= lim; i++) {
            res = (res + helper(n-i,i-1)) % mod;
        }
        return res;
    }
    int helper(int n) {
        memset(dp, -1, sizeof dp);
        return helper(n,n);
    }
    void helper(vector<int>& A, int n, int p, int& res) {
        if(n < 0) return;
        if(n == 0) {
            res += 1;
            return;
        }
        if(p == A.size()) return;
        helper(A,n-A[p],p+1,res);
        helper(A,n,p+1,res);
    }
public:
    int numberOfWays(int n, int x) {
        if(x == 1) return helper(n);
        vector<int> cand;
        for(int i = 1; ; i++) {
            int now = pow(i,x);
            if(now > n) break;
            cand.push_back(now);
        }
        int res = 0;
        helper(cand,n,0,res);
        return res;
    }
};