Get fewest number of values that satisfies all keys

user_4093473 0
Viewed 61

Say I have one of two setups

map[int][]int{
  19: {1, 2},
  20: {2, 3},
  233: {3}
}

or

map[int][]int{
  1: {19},
  2: {19, 20},
  3: {20, 233},
}

I would like to get an output that is the fewest number of values that satisfies the keys (in the first example)

There are two valid outputs for this example []int{1, 3} or []int{2,3}

Another example:

In:

map[int][]int{
  18: {1}
  19: {1, 2},
  20: {2, 3},
  233: {3}
}

Out: []int{1,3}

I've looked into DFS, but can't seem to wrap my head around setting it up to be able to get the solution. Maybe this could also be a set cover problem.

go algorithm
1 Answers

Each value is equivalent to the subset of the keys that it will satisfy.

You want the smallest set of values that cover all of the keys.

This is exactly the https://en.wikipedia.org/wiki/Set_cover_problem, which was one of the 21 original problems that were proven to be NP-complete.

user_5854110
Related