Doubt in approach of the problem

#1

How could we solve this problem using Permutations and Combinations. And how do I solve it recursively?
Here is my initial logic https://ide.codingblocks.com/s/143456

#2

Hi Dhanesh, let me know how did you reach the solution 2n -2.

#3

Hi, Sincere Apologies for late reply. Consider we have 3 friends A,B,C. A can pair up with B and C. B can pair up with only C. So here are 2 + 1 ways

#4

After it the last way is to be individual so total will be 2 + 1 + 1

#5

So for ‘N’ Friends answer will be (N-1) + (N-2) + (N-3) + … + 1 and additional + 1 of all being alone

#6

No problems :slight_smile:
I’ll try to help you out with this.
So according to me for 3 friends you can have the following ways :
a b and c remain alone.
a is alone and b pair c.
a pair b and c is alone.
a pair c and b is alone.

Now let us say you wanted to find the answer for N friends.
if n == 1 then we know ans(1) is 1.
similarly ans(2) is 2.
to find ans(N), let us say we knew the ans for total of N-1 and N-2 friends.
the Nth friend can choose to stay alone or make a pair with any of the other N-1 friends.
If he stays alone then remaining friends can be paired in a total of ANS(N-1) ways. If he wants to pair up with someone he has N-1 options with which he can make a pair with. So after he pairs up with some friend we are left with N-2 friends which can pair with each other in ANS(N-2) ways.

Therefore :
Ans(N) = Ans(N-1) + (N - 1) * Ans(N-2)
for example:
ans(3) = Ans(2) + (3-1)Ans(1)
ans(3) = 2 + 21 = 4.
Hope this helps :slight_smile:

#7

Hi, Thanks for your help. I implemented the problem using your approach with recursion as well as DP. But still I am getting wrong answer. Here is the link to my code : https://ide.codingblocks.com/s/146570

#8

I also tried using long long instead of int still getting WA

#9

Hi @Dhanesh when you tried using long long instead of int, did you also change the return type of the function makePairDp to long long instead of int.
Because to me the implementation seems correct except for the integer overflow.

#10

I used #define int long long int to replace all ints to long long int. Still getting WA. Link to my code https://ide.codingblocks.com/s/146592

#11

@Dhanesh you have made a typo in the recurrence equation, it should instead be
dp[i] = dp[i-1] + (i-1)*dp[i-2]. try fixing that and let me know.

#12

dp[i] = dp[i-1] + (i-1)*dp[i-2] this instead of dp[i] = dp[i-1] + (n-1)*dp[i-2].

#13

It worked, Thanks for your help :slight_smile: