CODEWITHSUNDEEP
arraysalgorithm
Saad
Saad

Reputation: 1360

Algorithm: Finding max subset of elements in array

I have an array arr containing pairs of elements. I need to find the largest subset from that array, such that, each pair wise element in that subset exists in the array arr.

e.g. let arr = [(a,b), (a,c), (a,d), (b,d)]
Then, the largest subset would be {a,b,d}, because all possible pair-wise combinations in the subset exists in arr.

Upvotes: 1

Views: 198

Answers (1)

user4668606
user4668606

Reputation:

This is equivalent to the problem of finding the largest complete component (maximum clique problem) in an undirected graph, where each pair represents an edge in the graph.

This problem is NP-hard, so there's no better approach than a simple brute-force-search. The implementation is either trivial or too complex to be posted here though, so you'll have to figure that out on your own.

Upvotes: 1

Related Questions