Sum of products of all subsets of any given array where size of subsets is 1 to n (detailed description given)

# SUM OF PRODUCT OF ALL SUBSETS OF ANY GIVEN ARRAY

# THIS PROGRAM ALSO CALCULATES SUM OF PRODUCT OF ALL SUBSETS OF SIZE 'K'

# EXAMPLE :-

# arr = [2,2,1]
# all subsets = [] , [2] , [2] , [1] , [2,2] , [2,1] , [2,1] , [2,2,1]
# subsets having :-
#         size 0 = []
#         sum of product of all size 0 subsets = 0

#         size 1 = [2] , [2] , [1]
#         sum of product of all size 1 subsets = 2+2+1 = 5

#         size 2 = [2,1] , [2,1] , [2,2]
#         sum of product of all size 2 subsets = 2+2+4 = 8

#         size 3 = [2,2,1]
#         sum of product of all size 3 subsets = 4

# Sum of all products = 0+5+8+4 = 17
# So answer is 17

# PROGRAM :-

n = int(input())    # Input size of array
k = int(input())    # Input size of subset
arr = list(map(int,input().split())) #Input array

# Now this program will calculate sum of product of all subsets of size 0 to size 'k'
# If you want to calculate for all subsets, simply put k=n

if k == 0:
    print('Sum of product of all subsets of size 0 = 0')
else:
    c = [0]*(max(arr)+1)
    for i in arr:
        c[i] += 1

    a = []
    for i in c:
        if i>0:
            a.append(i)

    n = len(a)
   
    dp = []
    dp.append(a+[sum(a)])
   
    for i in range(1,k):
        dp.append([])
        total = dp[i-1][-1]
        res = 0
        for j in range(n-i):
            total -= dp[i-1][j]
            temp = total*dp[0][j]
            res += temp
            dp[i].append(temp)
        dp[i].append(res)
   
    ans = 0
    for i in range(len(dp)):
        print('Sum of product of all subsets of size '+str(i+1)+' = '+str(dp[i][-1]))
        ans += dp[i][-1]
   
    print('\nAnswer :-',ans)