Friends Pairing Problem - wrong answer

#1

code link https://ide.codingblocks.com/s/161422

I have also written the explanation my approach and doubt in the comments in code .

#2

You have written wrong recursion.

long ways = countWays(persons -1 , dp)*2;

The correct recursive relation for this problem is :-

long ways = countWays(persons - 1, dp) + (persons -1) * countWays(persons - 2, dp);
#3

Please see if this resolves your issue.

#4

Sorry I don’t see how this recursion relation fits in the problem.
perhaps can you see the explanation of what I’m intending to do and then guide me again?

#5

I can tell you how this recursive relation fits in the problem. See first every friend has a choice to go alone or go in a pair.

long ways = 0;

if he goes alone.

countWays(persons - 1, dp)

if he goes in a pair. he can go in pair with (n - 1) other people.

(persons -1) * countWays(persons - 2, dp)

so thats why i gave you the recursive relation.

long ways = countWays(persons - 1, dp) + (persons -1) * countWays(persons - 2, dp);

If still unsure, you can refer https://www.geeksforgeeks.org/friends-pairing-problem/ for clarity.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.