javascript - 设置覆盖 : Find a set of arrays that overlap the elements of a target array

Question

假设我有一个数组，A(可排序，如果有帮助的话)

我有一组数组，B、C、D 等等(都是可排序的)，所有这些都可能部分或完全重叠数组 A。

我想找到最小的一组数组 B、C、D 等...完全重叠数组 一个。返回第一个匹配项。

例如，

const A = [1, 2, 3, 4, 'a', 'b', 'c'];

const B = [1, 3, 4, 5, 10];
const C = [1, 3, 5, 'a', 'b']
const D = [2, 4, 'a', 'b', 'c'];
const E = [1, 2, 'b', 'c'] 

findSmallestSet(A, [B, C, D, E]);
// => [B, D]

旁白:我最初的问题是找到与目标节点树完全重叠的节点树，但我认为上面提出的问题可能是一个更简单的解决方案。

Answer 1

这就是所谓的“设置封面”问题。它是 NP 完全的，并且经过充分研究。 “正确答案”取决于输入的大小以及您是否可以接受近似值。