如何find给定数组的所有可能的子集？
我想在C＃或C ++中提取一个数组的所有可能的子集，然后计算所有子集数组各自元素的总和，以检查它们中有多less个与给定数相等。
我正在寻找的是algorithm。 我理解这里的逻辑，但是现在我还没能实现这个逻辑。
考虑N元素的集合S以及给定的子集，每个元素既可以属于该子集也可以不属于该子集。 因此是2^N可能的子集（如果包含原始集合和空集合），并且存在从0到2^N之间的x的二进制表示中的位到在S第x个子集中的元素的直接映射。
一旦你已经弄清楚如何枚举给定子集的元素，添加值是很简单的。
对于大Nfind等于总t子集，一个优化可能是logging那些超过t子集，而不是testing那些超集的超集。 testing集号x是否是集合y的超集可以通过单个按位操作和整数比较来实现。
你正在寻找的是所谓的功率集 。 Rosetta Code有很多不同的实现，但是这里是他们的C ++代码（它们使用的是一个向量而不是一个数组，但是它应该很容易翻译）。
#include <iostream> #include <set> #include <vector> #include <iterator> typedef std::set<int> set_type; typedef std::set<set_type> powerset_type; powerset_type powerset(set_type const& set) { typedef set_type::const_iterator set_iter; typedef std::vector<set_iter> vec; typedef vec::iterator vec_iter; struct local { static int dereference(set_iter v) { return *v; } }; powerset_type result; vec elements; do { set_type tmp; std::transform(elements.begin(), elements.end(), std::inserter(tmp, tmp.end()), local::dereference); result.insert(tmp); if (!elements.empty() && ++elements.back() == set.end()) { elements.pop_back(); } else { set_iter iter; if (elements.empty()) { iter = set.begin(); } else { iter = elements.back(); ++iter; } for (; iter != set.end(); ++iter) { elements.push_back(iter); } } } while (!elements.empty()); return result; } int main() { int values[4] = { 2, 3, 5, 7 }; set_type test_set(values, values+4); powerset_type test_powerset = powerset(test_set); for (powerset_type::iterator iter = test_powerset.begin(); iter != test_powerset.end(); ++iter) { std::cout << "{ "; char const* prefix = ""; for (set_type::iterator iter2 = iter->begin(); iter2 != iter->end(); ++iter2) { std::cout << prefix << *iter2; prefix = ", "; } std::cout << " }\n"; } }
输出：
{ } { 2 } { 2, 3 } { 2, 3, 5 } { 2, 3, 5, 7 } { 2, 3, 7 } { 2, 5 } { 2, 5, 7 } { 2, 7 } { 3 } { 3, 5 } { 3, 5, 7 } { 3, 7 } { 5 } { 5, 7 } { 7 }
这是我4/5年前的大学项目之一，我不能很好地提醒这个algorithm。 正如我看到＆我的记忆服务它使用一个数组作为原始的集合和一个位掩码来指示当前子集中存在的元素。
这是来自存档的未经testing的代码：
#include <iostream> #ifndef H_SUBSET #define H_SUBSET template <class T> class Subset { private: int Dimension; T *Set; bool *Bitmask; public: Subset(T *set, int dim); ~Subset(void); void Show(void); void NextSubset(void); void EmptySet(void); void FullSet(void); int SubsetCardinality(void); int SetCardinality(void); T operator[](int index); }; template <class T> int Subset<T>::SetCardinality(void) { return Dimension; } template <class T> int Subset<T>::SubsetCardinality(void) { int dim = 0; for(int i = 0; i<Dimension; i++) { if(Bitmask[i]) { dim++; } } return dim; } template <class T> void Subset<T>::EmptySet(void) { for(int i = 0; i<Dimension; i++) { Bitmask[i] = 0; } return; } template <class T> void Subset<T>::FullSet(void) { for(int i = 0; i<Dimension; i++) { Bitmask[i] = 1; } return; } template <class T> void Subset<T>::NextSubset(void) { int i = Dimension - 1; while(!Bitmask[i]&&i>=0) { i--; if(i<0) { break; } } if(i>=0) { Bitmask[i] = !Bitmask[i]; } for(int j = i+1; j < Dimension; j++) { Bitmask[j] = !Bitmask[j]; } return; } template <class T> void Subset<T>::Show(void) { std::cout << "{ "; for(int i=0; i<Dimension; i++) { if(Bitmask[i]) { std::cout << Set[i] << ", "; } } std::cout << "}"; return; } template <class T> Subset<T>::Subset(T *set, int dim) { Set = new T[dim]; Bitmask = new bool[dim]; Dimension = dim; for(int i=0; i<dim; i++) { Set[i] = set[i]; Bitmask[i] = true; } } template <class T> Subset<T>::~Subset(void) { delete [] Set; delete [] Bitmask; } #endif // H_SUBSET
如果这是你的功课，你正在杀死自己的兄弟;）
你做;
A）真的想find所有可能的子集？
要么
B）希望find一个数组中有多less个元素可以组合成一个给定的数字，并且看到A）是解决问题的一个步骤？
如果它是A），那么它非常简单，但是可能的子集的数量变得非常快。
如果是B），那么你应该先sorting数组，然后从那里开始工作。
