编程之美 二十四点

Use sets to keep unique and Binary Form 1111 to the possible results.  The code is :

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class Solution {
 public:
  set<double> status[16];
  typedef set<double>::iterator ITER;
  void f(int x, vector<int>& vec) {
    for (int i = 1; i <= x / 2; ++i) {
      if ((x & i) == i) {
        for (ITER j = status[i].begin(); j != status[i].end(); ++j)
          for (ITER k = status[x-i].begin(); k != status[x-i].end(); ++k) {
            status[x].insert((*j) * (*k));
            status[x].insert((*j) + (*k));
            status[x].insert((*j) - (*k));
            status[x].insert((*k) - (*j));
            if ((*k) != 0)
              status[x].insert((*j) / (*k));
            if ((*j) != 0)
              status[x].insert((*k) / (*j));
          }
      } 
    }
  }
  void init(const vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i)
      status[(1 << i)].insert((double)vec[i]);
  }
  bool getSum24(vector<int>& vec) {
    init(vec); 
    for (int i = 1; i <= 15; ++i)
      f(i, vec);
    return status[15].find(24) != status[15].end() ? true : false;
  }
};


int main() {
  int a[] = {1, 1, 1, 1};
  Solution s;
  vector<int> vec(a, a+4);
  bool res = s.getSum24(vec);

  return 0;
}