数组的位和子集
数组的位和子集
提问于 2015-06-06 12:34:45
有人能给出一个如何处理这个问题的提示吗？
给定数组A，是否有数组A的子集，如果我们这样做了，以及该子集的所有元素的子集，那么输出应该是2的幂。
我曾经想过生成一个幂集并进行求解，但是它的复杂度很差(2^n)。
提前谢谢。
Stack Overflow用户
回答已采纳
发布于 2015-06-06 13:11:35
你可以从不同的角度来看待它:选择两种力量。我们能生成它吗？
这个问题很容易回答。从设置了与2的幂相对应的位的集合中提取所有项。计算所有这些的和。结果必须通过构造具有我们所寻找的位集，但它可能有也可能没有任何其他位集。如果它也有其他位，那么选择其他一些(较小的-您不能选择任何额外的项目，因为他们没有目标位集)子集也不能工作，它可能只有更多的错误位设置，因为它将有较少的可能性取消位。
只要对所有可能的二次幂都这样做，这只是集合中最大整数中的位数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30682927
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号