Problem Statement:
Consider a 1D array of size N with distinct elements. Now, we have to select minimum number subsets, say K, of fixed size M from it (where, M < N) such that every possible pairings of elements in the original array is present in these K subsets.
Example:
array = [1,2,3,4]
M = 3
the conditions dictate that these pairings must happen : 1<->2, 1<->3, 1<->4, 2<->3, 2<->4, 3<->4
the least possible subsets satisfying the conditions are
[1,2,3] (1<->2, 1<->3, 2<->3)
[1,2,4] (1<->4, 2<->4)
[3,4,X] (3<->4, where X can be either 1 or 2)
Thus, the min value of K is 3
What would be a general method to find these subsets for any given array of size N and fixed subset size M?