# 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