如何查找给定数组的所有可能子集？

我想在C#或C++中提取所有可能的数组子集,然后计算所有子集数组各自元素的总和,以检查它们中有多少等于给定数字.

我要找的是算法.我确实理解这里的逻辑,但我现在还没能实现这个.

考虑一组S的N元素,和给定子集,各元素或者或不属于该子集.因此是2^N可能的子集(如果包括原始和空集),并且存在从在的二进制表示中的位直接映射x之间0并2^N在所述元件x的个子集S.

一旦你弄清楚如何枚举给定子集的元素,添加值很简单.

为了找到这等于总的子集t为大N,一个优化可能是记录那些超过子集t,并没有测试任何这是那些适当超集.测试集合数x是否是集的超集y可以通过单个按位运算和整数比较来实现.

您正在寻找的是电源组. Rosetta Code有很多不同的实现,但这里是他们的C++代码(他们使用向量而不是数组,但它应该很容易翻译).

#include 
#include 
#include 
#include 

typedef std::set set_type;
typedef std::set powerset_type;

powerset_type powerset(set_type const& set)
{
  typedef set_type::const_iterator set_iter;
  typedef std::vector 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年前的大学项目之一,我无法很好地提醒算法.正如我所看到的那样,我的记忆服务是使用数组作为原始集合和位掩码来指示当前子集中存在哪些元素.
这是来自存档的未经测试的代码:

#include 

#ifndef H_SUBSET
#define H_SUBSET

template 
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 
int Subset::SetCardinality(void) {
    return Dimension;
}

template 
int Subset::SubsetCardinality(void) {
    int dim = 0;
    for(int i = 0; i
void Subset::EmptySet(void) {
    for(int i = 0; i
void Subset::FullSet(void) {
    for(int i = 0; i
void Subset::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 
void Subset::Show(void) {
    std::cout << "{ ";
    for(int i=0; i
Subset::Subset(T *set, int dim) {
    Set = new T[dim];
    Bitmask = new bool[dim];
    Dimension = dim;
    for(int i=0; i
Subset::~Subset(void) {
    delete [] Set;
    delete [] Bitmask;
}
#endif // H_SUBSET

如果这是你的功课,那你就是自杀了;)