Hello everyone,
I was trying to solve this Power sum problem but wasn’t able to solve it. I tried reading the editorial but couldn’t get it.

I’m not sure what backtracking is and how it works?

Can you please discuss your approach?
Thank you
Hello everyone,
I was trying to solve this Power sum problem but wasn’t able to solve it. I tried reading the editorial but couldn’t get it.
I’m not sure what backtracking is and how it works?
Can you please discuss your approach?
Thank you
If you wanna read about Backtracking, read here and here and try to solve the Famous Nqueen problem.
I will soon share the solution for Your problem, probably tonight because i’m running busy at the moment.
Well, Your problem had two solutions, one recursive(slower) and one dp solution.
Recursive Solution: sum(X, N, 1) gives the answer.
static int sum(int X, int N, int num){
int value = X  (int)Math.pow(num, N);
if(value < 0)return 0;
if(value == 0)return 1;
return sum(X, N, num+1) + sum(value,N,num+1);
}
Refer DP solution here, though try forming dp solution from above recursive one first!!.
Thank you I’ll wait for your solution
Thanks but can you please tell me how
return sum(X, N, num+1) + sum(value,N,num+1);
this works
Sum(X,N,num+1) gives number of ways, X can be formed using nth power of numbers greater than num, without including nTh power of num.
Sum(value, N,num+1) gives the same, while including Nth power of num.