Input  : n = 3
Output : 4
Explanation:
{1}, {2}, {3} : all single
{1}, {2, 3} : 2 and 3 paired but 1 is single.
{1, 2}, {3} : 1 and 2 are paired but 3 is single.
{1, 3}, {2} : 1 and 3 are paired but 2 is single.
Note that {1, 2} and {2, 1} are considered same.

f(n) = ways n people can remain single 
       or pair up.

For n-th person there are two choices:
1) n-th person remains single, so only 1 way so  we recur 
   for remaining i.e f(n - 1)   or you can say 1*f(n-1)
2) n-th person pairs up with any of the 
   remaining n - 1 persons. So apart from the 2 people forming a pair for remaining n-2 persons we We get (n - 1) * f(n - 2) ways

Therefore we can recursively write f(n) as:
f(n) = f(n - 1) + (n - 1) * f(n - 2)

 int countFriendsPairings(int n) 
    { 
        
        if(n<=2) return n;
        return countFriendsPairings(n-1)+ (n-1)*countFriendsPairings(n-2);
    }

int solve(int n, vector < int > & dp) {

   if (n <= 2) return n;

   if (dp[n] != -1) return dp[n];

   return dp[n] = solve(n - 1, dp) + (n - 1) * solve(n - 2, dp);
 }

 int countFriendsPairings(int n) {

   vector < int > dp(n + 1, -1);
   dp[0] = dp[1] = 1;
   return solve(n, dp);
 }

 int countFriendsPairings(int n) 
    { 
        vector<int> dp(n+1,0);
        dp[0]=1;  // null subset
        dp[1]=1;  // 1 way possible
        
        for(int i=2;i<=n;i++)
        {
            dp[i]=(1*dp[i-1] + (i-1)*dp[i-2];
        }
        return dp[n];
    }

    int countFriendsPairings(int n) 
    { 
        if(n<=2) return n;
        int a =1, b = 2, c = 2;
        for(int i=3;i<=n;i++){
            c = 1*b + (i-1)*(a);
            a = b;
            b = c;
        }
        return c;
    }