Consider an array $ a$ , where elements are numbers. Consider all subsequence of $ a$ . For each subsequence $ s$ , we find an element $ k$ with the largest number of occurrences in $ s$ (if there are several options, choose the smallest such $ k$ ).
Problem: for each number $ k$ , find the number of subsequences of $ a$ for which $ k$ is the chosen number.
Input: [1, 2, 2, 3] Output: 1 -> 6 (, [1, 2], [1, 2'], [1, 3], [1, 2, 3], [1, 2', 3]) 2 -> 8 (, [2'], [2, 3], [2', 3], [2, 2'], [1, 2, 2'], [2, 2', 3], [1, 2, 2', 3]) 3 -> 1 ()
My idea is that, I make a map $ cnt$ where $ cnt[x]$ is number of times $ x$ occurred in array $ x$ . I am trying to find the answer for $ k$ then i will create a map $ temp$ where $ temp[i]=\min(cnt[k], cnt[i])$ . Then consider the value of $ cnt[k]$ to be $ m$ then in a subset element $ k$ can occur from $ 0$ to $ m$ times and using this i will find answer for all of its occurrences from $ 0$ to $ m$ which is a simple number of sub sets problem and finally i will have my answer.
But the complexity of my algorithms is bad as it is quadratic or worse. Can it be improved?