Finding unique combinations that fulfill a given set of conditions

I'm trying to find the unique combinations that fulfill the given criteria, sorted by cost. An example:

Criteria: [A, B, C, D]
Entities: [
   E1 = (costs = 5, covers = [A, B, E]),
   E2 = (costs = 5, covers = [C, D]),
   E3 = (costs = 2, covers = [B, C]),
   E4 = (costs = 1, covers = [D]),
   E5 = (costs = 5, covers = [B, D]),
   E6 = (costs = 3, covers = [B, D]),
   E7 = (costs = 0, covers = [E])
]

Expected output (cost to combination): [
  (8, [E1, E3, E4])
  (10, [E1, E2])
  (10, [E1, E3, E6])
  (12, [E1, E3, E5])
]

While language doesn't really matter to me, I've set up an example in Kotlin to get started easily: https://pl.kotl.in/V93dnrvbF

I'm currently working on applying a critical path algorithm to find the 'cheapest' solution, but ideally I'd get a collection of 'all' possible solutions, ordered by cost, as I need to weigh cost other criteria further down the line in the application, meaning the cheapest solution here might not be the end result.

Note: by 'all' I mean all 'sensible' results, e.g. (8 -> [E1, E3, E4]) but not (8 -> [E1, E3, E4, E7]). All criteria need to be met in the resulting combination, but overlapping in covered criteria is allowed.

Context: I don't expect the entities list to be very large in reality (0~20), but there's likely to be a lot of of overlap in the covered criteria. I've tried to include this in the example. My application is written in Kotlin.

Solution

Here's a full working example that I came up with

data class Entity(val costs: Int, val covers: Set<String>, val name: String) {
    override fun toString() = name
}

data class Result(val cost: Int, val entities: Set<Entity>) {
    override fun toString() = "($cost, $entities)"
}

val E1 = Entity(5, setOf("A", "B", "E"), "E1")
val E2 = Entity(5, setOf("C", "D"), "E2")
val E3 = Entity(2, setOf("B", "C"), "E3")
val E4 = Entity(1, setOf("D"), "E4")
val E5 = Entity(5, setOf("B", "D"), "E5")
val E6 = Entity(3, setOf("B", "D"), "E6")
val E7 = Entity(0, setOf("E"), "E7")
val entities = setOf(E1, E2, E3, E4, E5, E6, E7)

fun findUniqueCombinationsSortedByCost(criteria: Set<String>, entities: Set<Entity>): List<Result> {
    val matches = find(criteria, entities)
    return matches?.map { set -> Result(set.sumOf { it.costs }, set) }?.sortedBy { it.cost }
        ?: emptyList() // Implementation
}

fun find(criteria: Set<String>, entities: Set<Entity>): Set<Set<Entity>>? {
    val reduced = entities.filter { e -> e.covers.intersect(criteria).isNotEmpty() }
    if (reduced.isEmpty()) return null
    if (reduced.size == 1) {
        return if ((criteria - reduced.first().covers).isEmpty()) {
            setOf(reduced.toSet())
        } else {
            null
        }
    }
    val result = mutableSetOf<Set<Entity>>()
    for (i in reduced.indices) {
        if ((criteria - reduced[i].covers).isEmpty()) {
            result.add(setOf(reduced[i]))
        } else {
            val results = find(criteria - reduced[i].covers, reduced.subList(i + 1, reduced.size).toSet())
            if (results != null) {
                for (sets in results) {
                    result.add(setOf(reduced[i]) + sets)
                }
            }
        }
    }
    return result
}

fun main() {
    println(
        findUniqueCombinationsSortedByCost(
            criteria = setOf("A", "B", "C", "D"),
            entities = entities
        )
    )
}

I'm not sure if my algorithm is very efficient but I believe it gets the job done. It prints

[(8, [E1, E3, E4]), (10, [E1, E2]), (10, [E1, E3, E6]), (12, [E1, E3, E5])]