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

general
, ,
1

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

2

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
3

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

4

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
5

Thanks but can you please tell me how

return sum(X, N, num+1) + sum(value,N,num+1);

this works

6

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.