java - 关于如何从 char 字符串中获取所有子集而不覆盖所有不同字母的算法是什么？

Question

我最近一直在努力解决一个子集算法问题。

如何从一个字符字符串中获取所有子集？

条件:每个子集不能覆盖原始字符串的所有不同字母。

例如abbc, [a,b,c] -> 输出-> a, b, c, ab, abb, bbc, bb, bc

子集:{abc} 和 {abbc} 应该被删除!

我最初的想法是将原始字符串预处理为a1b2c1，然后递归，每个递归层处理一个不同的字母。在最后一层，像这里，我们需要进程c，是否将c放入子集取决于前面层传递的信息。

我不确定我的想法是否好，有人对这个问题有想法吗？

Answer 1

如果您只需要覆盖字母(即不同对象的数量小于 26，包括在内)，那么您可以制作一个代表“宇宙”的位集。此位集将在字母表中的字母位置设置 1，在所有其他位置设置零。

您可以按照您描述的方式递归，向下传递 universe 位集以及 soFar 位集，它表示已添加的字母远的。当您到达 soFar 等于 universe 的调用时，您知道您的位集将包含所有可用字母，并且不添加它到结果列表。