Counting pairs when a person can form pair with at most one

We need count the number of ways in which n participants participating in the coding competition.

Examples:

Input : n = 2
Output : 2
2 shows that either both participant 
can pair themselves in one way or both 
of them can remain single.

Input : n = 3 
Output : 4
One way : Three participants remain single
Three More Ways : [(1, 2)(3)], [(1), (2,3)]
and [(1,3)(2)]

1) Every participant can either pair with another participant or can remain single.
2) Let us consider X-th participant, he can either remain single or
he can pair up with someone from [1, x-1].

// Number of ways in which participant can take part.
#include<iostream>
using namespace std;

int numberOfWays(int x)
{
    // Base condition 
    if (x==0 || x==1)     
        return 1;

    // A participant can choose to consider
    // (1) Remains single. Number of people 
    //     reduce to (x-1)
    // (2) Pairs with one of the (x-1) others.
    //     For every pairing, number of people 
    //     reduce to (x-2). 
    else 
        return numberOfWays(x-1) + 
               (x-1)*numberOfWays(x-2);
}

// Driver code
int main()
{
    int x = 3;
    cout << numberOfWays(x) << endl;
    return 0;
} 

Output:

2

Since there are overlapping subproblems, we can optimize it using dynamic programming.

// Number of ways in which participant can take part.
#include<iostream>
using namespace std;

int numberOfWays(int x)
{
    int dp[x+1];
    dp[0] = dp[1] = 1;

    for (int i=2; i<=x; i++)
       dp[i] = dp[i-1] + (i-1)*dp[i-2];

    return dp[x];
}

// Driver code
int main()
{
    int x = 3;
    cout << numberOfWays(x) << endl;
    return 0;
} 

Output:

2

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/counting-pairs-person-can-form-pair-one/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar