BackTracking - The power Sum(HackerRank's problem) Recursion

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

If you wanna read about Backtracking, read here and here and try to solve the Famous N-queen problem.

I will soon share the solution for Your problem, probably tonight because i’m running busy at the moment.

1 Like

Thank you I’ll wait for your solution :slight_smile:

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!!.

1 Like

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.