×

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

 0 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 2★kunnu120 518●9 accept rate: 5%

 1 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 3.9k●28●95 accept rate: 22% 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) kunnu1202★ 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)
 1 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. answered 23 Dec '17, 12:14 3.9k●28●95 accept rate: 22% Thank you I'll wait for your solution :) (23 Dec '17, 13:19) kunnu1202★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×348
×310
×104

question asked: 23 Dec '17, 11:35

question was seen: 1,688 times

last updated: 24 Dec '17, 17:29