The Power Sum Time : O(xn) Space : O(xn) 1234567891011int dp[1000][1000];int helper(int X, int p, int now) { if(dp[X][now] != -1) return dp[X][now]; if(pow(now, p) > X) return 0; if(pow(now, p) == X) return 1; int& res = dp[X][now] = helper(X - pow(now, p), p, now + 1) + helper(X, p, now + 1); return res;}int powerSum(int X, int N) { return helper(X, N, 1);}