如何找到一个给定数组的所有可能的子集？ [英] How to find all possible subsets of a given array?

问题描述

欲提取所有可能的子集的阵列的在C＃或C ++，然后计算所有子组阵列各元素的总和，以检查有多少都是等于给定的次数。

我在找的是算法。我明白这里的逻辑，但我一直没能到现在实现这一点。

解决方案

考虑到 N A组取值 元素和一个给定的子集，每个元件或者或不属于该子集。因此有 2 ^ N 可能的子集（如果包括原来的空套），并有从的二进制再presentation位直接映射<在 0 X >和 2 ^ N 在元素 X 个的S子集。

一旦你制定出如何枚举一个给定的子集的元素，增加值也很简单。

有关发现里面一共有等于子集 T 为大 N ，一是优化可能会记录这些子集这超过 T ，并没有测试任何这是那些正确的超集。测试是否设置数量 X 是集的超集是可以用一个位运算和整数比较来实现的。

I want to extract all possible sub-sets of an array in C# or C++ and then calculate the sum of all the sub-set arrays' respective elements to check how many of them are equal to a given number.

What I am looking for is the algorithm. I do understand the logic here but I have not been able to implement this one by now.

解决方案

Considering a set S of N elements, and a given subset, each element either does or doesn't belong to that subset. Therefore are 2^N possible subsets (if you include the original and empty sets), and there is a direct mapping from the bits in the binary representation of x between 0 and 2^N to the elements in the xth subset of S.

Once you've worked out how to enumerate the elements of a given subset, adding the values is simple.

For finding subsets which equal a total t for large N, one optimisation might be to record those subsets which exceed t, and not test any which are proper supersets of those. Testing whether set number x is a superset of set y can be achieved with a single bitwise operation and an integer comparison.

这篇关于如何找到一个给定数组的所有可能的子集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！