如果我有一组值(我称之为 x)和 x 的多个子集:
计算并集等于 x 但没有一个子集相互交叉的所有可能组合的最佳方法是什么。
一个例子可能是:
如果 x 是数字 1 到 100 的集合，并且我有四个子集:
- a = 0-49
- b = 50-100
- c = 50-75
- d = 76-100
那么可能的组合是:
- a+b
- a + c + d
最佳答案
你描述的是Exact cover问题。一般的解决方案是 Knuth 的 Algorithm X , 与 Dancing Links算法是具体实现。
关于求解集合问题的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1452143/