我最近一直在努力解决子集算法的问题。
如何从一个字符串得到所有的子集?
条件:每个子集不能包含原始字符串的所有不同字母。
例如:abbc， [a,b,c] -> output-> a,b,c, ab, abb, bbc, bb, bc
子集:{abc}和{abbc}应该被删除!
我最初的想法是将原始字符串预处理为a1b2c1，然后递归，每个递归层处理一个不同的字母。在最后一层，就像这里，我们需要进程c，我们是否应该把c放在子集中取决于前一层传递下来的信息。
我不确定我的想法好不好，有人对这个问题有什么想法吗?如果你只需要覆盖字母(即不同对象的数量在26以下，包括在内)，那么你可以创建一个代表"宇宙"的位集。这个位集将使1位于字母表中的一个字母的位置，而其他所有位置都为零。
您可以按照您描述的方式递归地进行，向下传递universe位集，以及soFar位集，它表示到目前为止添加的字母。当您到达soFar等于universe的调用时，您知道您的位集将包含所有可用的字母，并且不将其添加到结果列表中。
在最坏的情况下，您将不得不处理所有2^n个子集，因此我认为您没有更好的时间明智。这样看来，你的答案就很好了。
需要传递给下一个递归步骤的唯一信息是到目前为止您是否选择了所有不同的字符。这只需要一个比特就可以完成。下面是一个例子:
将值和计数对表示为v[i]和c[i]。设n表示这种配对的数目。递归函数的状态可以定义为
F(i, b) =返回值> v[i]的所有子集。如果这些子集不包含所有不同的成员，则B = 1。F(n, b)是上述递归的平凡解。
查找F(0, 1)
当然，你必须从j = 0迭代到c[i]来考虑所有可能的情况，也就是说，子集应该包含多少个v[i]。对于j =0或b=0，下一个递归集合将有b=0否则应为1。
这将生成您所查找的所有子集。