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.

Solution 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.

Solution 2

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 }

Solution 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 ;)

Solution 4

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.

View more solutions

Comments

[Mobin]

can any1 give me the algorithm to find all possible subsets. i had this logic but i am not able to make it work by now thats why i am trying to find some codes:s

[sepehr]

google for code examples, this subset thing is a popular problem.

[Bart Kiers]

Pete, isn't it between 0 and (2^N)-1?

[Pete Kirkham]

The range [0, 2^N) inclusive, exclusive.

[neojb1989]

Hello! 3 years later and your code is wanting to be used! I am trying to adapt this to do something similar with a vector of ints instead of the int values[4] you use. Can you help :) ?