How to find all possible subsets of a given array?

Question

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. :s

Answer 1

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.

Answer 2

Do you;

A) Really want to find all of the possible subsets?

or

B) Wish to find how many elements in an array can be combined to equal a given number, and see A) as a step towards the solution?

If it's A) then it's quite straightforward but the number of possible subsets becomes ridiculously large very quickly.

If it's B) then you should sort the array first and work from there.

Answer 3

It's been one of my college projects 4/5 years ago, and I can't remind the algorithm well. As I see & my memory serves it's using an array as the original set and a bitmask to indicate what elements are present in the current subset.
here's the un-tested code from the archive:

#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

And if it's your homework, you're killing yourself bro ;)
update: I recommend to use the code of Bill the Lizard below.

Answer 4

What you're looking for is called the power set. Rosetta Code has a lot of different implementations, but here's their C++ code (they use a vector instead of an array, but it should be pretty easy to translate).

#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";
  }
}

Output:

{  }
{ 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 }

Answer 5

well finding all the subsets is simple, just check this code here: http://worldofbrock.blogspot.com/2009/10/how-to-find-subsets-of-array.html to find the sums, just add the numbers up instead of printing. hope this helps you.