Given n friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up.

Examples:

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.

Thinking process:

for n =0 , there are no friends to pair , so return 0 for n=1, there is only one person, only way is that he being single, so return 1 for n=2, there are two ways. {{1}, {2}} and {{1,2}} for n =3 , there are 4 ways {{1},{2},{3}} {{1,2},{3}} {{1,3},{2}} {{2,3},{1}} for n=4, There are 10 ways. for n=5, there two ways. One is we can keep the 5th member single and pair others and the other one is pair the 5th guy with some guy

= f[4] (5th guy is single and we pair the rest) + (n-1)C1 * (f[3]) (select one from the remaining guys and pair with him and multiply it with the number of ways of the rest) f[n] = f[n-1] + (n-1)*f[n-2]

def findpairs(num):
    if num<=0:
        return 0
    if num==1:
        return 1
    if num==2:
        return 2
    res = [0]*(num+1)
    res[0] = 0
    res[1] = 1
    res[2] = 2

    for i in range(3,num+1):
        res[i] = res[i-1] + (i-1)*res[i-2]

    return res[num]