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. 1) I'm not sure what backtracking is and how it works? 2) Can you please discuss your approach? Thank you asked 23 Dec '17, 11:35

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!!. answered 23 Dec '17, 18:24
Thanks but can you please tell me how return sum(X, N, num+1) + sum(value,N,num+1); this works
(24 Dec '17, 08:29)
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.
(24 Dec '17, 17:29)
