some algorithmic puzzles, tutorials, interview questions... and stuff...

Friday, October 23, 2009

How to find subsets of an array

The problem statement: given an array of integers, for example (2, 5, 8, 10), how do you print all the subsets of this array. By all the subsets, I mean:

   1:  empty set
   2:  10
   3:  8
   4:  8 10
   5:  5
   6:  5 10
   7:  5 8
   8:  5 8 10
   9:  2
  10:  2 10
  11:  2 8
  12:  2 8 10
  13:  2 5
  14:  2 5 10
  15:  2 5 8
  16:  2 5 8 10

Well the answer is simple recursively: for each number in the array, compute recursively all the subsets without including it. Then include it and compute again all the subsets.

   1:  void subsets_recursive(int* vec, int size, int index, vector<int>* subset) {
   2:      if (index == size) { //print if we reached the end
   3:          if (subset->size() == 0)
   4:              cout << "empty set";
   5:          for (int i = 0; i < subset->size(); i++)
   6:              cout << subset->at(i) << " ";
   7:          cout << endl;
   8:          return;
   9:      }
  10:      int n = subset->size();
  11:      //first print all the subsets without including the number
  12:      subsets_recursive(vec, size, index + 1, subset);
  13:      //clear the numbers that we added in the previous subsets
  14:      while (subset->size() != n)
  15:          subset->pop_back();
  16:      //add the number to the subset and print all subsets including it
  17:      subset->push_back(vec[index]);
  18:      subsets_recursive(vec, size, index + 1, subset);
  19:  }

Iteratively it's a different story. Complexity for this (both recursively and iteratively) is O(2n), where "n" is the size of the array. This means we have to iterate 2n times. As it turns out, there's a trick involved: take each number i from 0 to 2n and check each bit. If bit k from number i is 1, then consider arrayk to be in the current subset. Too bad I didn't think of this during the interview. Here it is:

   1:  void subsets_iterative(int* vec, int size) {
   2:      int n = pow((double)2, (double)size);
   3:      vector<int> currentSubset;
   4:      for (int i = 0; i < n; i++) {
   5:          currentSubset.clear();
   6:          for (int j = 0; j < size; j++)
   7:              if (((i >> j) & 1) != 0)
   8:                  currentSubset.push_back(vec[j]);
   9:          if (currentSubset.empty())
  10:              cout << "empty set";
  11:          for (int i = 0; i < currentSubset.size(); i++)
  12:              cout << currentSubset.at(i) << " ";
  13:          cout << endl;
  14:      }
  15:  }

4 comments:

  1. no entiendo nada....
    yo quiero saber el número de subconjuntos de el conjunto A={x pertenece a números naturales / 4<x a la potencia 2<144}
    osea A={x pertenece a números naturales/2<x<12}
    porfa dime la respuesta!!!!
    ES IMPORTANTE!!!!!!!!!!

    ReplyDelete
  2. I don't understand anything

    ReplyDelete
  3. Minor improvement in your second piece of code:
    1. you can use i from 1 to n, because when i=0, there is no chance that something to be printed
    2. you use i inside the loop i. Should use another variable instead.

    ReplyDelete