#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int findleast(int *takings, int takingsLength, vector<int> &list, int daysLeft, int start, int currTotal, vector<int> &result, int expected)
{
 if (daysLeft == 0)
  return currTotal;
 
 int closest = INT_MAX;
 int closestIndex = start;
 for (int i = start; i < takingsLength - daysLeft; ++i)
 {
  list.push_back(takings[i]);
  int nextClosest = findleast(takings, takingsLength, list, daysLeft-1, i+1, currTotal + takings[i], result, expected);
  list.pop_back();
 
  if (abs(nextClosest) < abs(closest))
  {
   closest = nextClosest;
   closestIndex = i;
  }
 
  if (nextClosest == expected)
  {
   result.push_back(takings[i]);
   break;
  }
 }
 
 return closest;
}
 

void print_int (int out)
{
 cout << out << endl;
}
 
int main(int argc, char* argv[])
{
 int monthsTakings[] = {-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101, 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8,};
 
 vector<int> list;
 vector<int> result;
 
 int numDays = 9;
 int best = findleast(monthsTakings, 31, list, numDays, 0, 0, result, 0);
 cout << "Best result: " << best << endl;
 result.clear();
 findleast(monthsTakings, 31, list, numDays, 0, 0, result, best);
 
 for_each(result.begin(), result.end(), print_int);
 
 return 0;
}