You are given an N by M matrix, each element in the matrix represents a different type cake.
You have X friends, each friend has some prefrences, for example friend 1 likes cake of type 0, 7, 10.
Friend 2 likes cakes of type 2, 7, 10.
etc.
Each friend will take one piece of cake, what is the maximum number of friends whom you can satisfy based on their preferences.
I coded brute force approach of trying evey single permutation.
For example, if friend one has preferences of 0,7,10. Then try each one, mark as taken, and keep track of the max.
You can use dp to reduce it to number of subsets 2^(N x M) x X, but given the constraints it is still not efficient.
Do you know of any other way to improve efficiency?