C++ solution of the "easiest hard problem", the partition problem. (the problem itself and algorithm described on wikipedia). It includes a file called Array2D.h (another one of my gists), which is just a wrapper around a dynamic 2d array which deletes the array in the destructor.

PartitionProblem

//////////////////////////
// Nathan Park (age 21) //
// August 4, 2013       //
//////////////////////////

#include <iostream>
#include <fstream>
#include <vector>
#include <numeric> // std::accumulate

#include "Array2D.h"

int main();
void ReadInput(std::vector<int> & array);
void InitTopRowToTrue(Array2D<bool> & P);
void InitLeftMostColToFalseExceptForP00(Array2D<bool> & P);
bool FindPartition(const std::vector<int> & S);

// http://en.wikipedia.org/wiki/Partition_problem
int main()
{
  std::vector<int> elements;
  ReadInput(elements);
  std::cout << "Partition Exists: " << FindPartition(elements);

  return 0;
}


void ReadInput(std::vector<int> & array)
{
  int val;
  while (std::cin >> val)
    array.push_back(val);
}

void InitTopRowToTrue(Array2D<bool> & P)
{
  for (unsigned i = 0; i < P.mCols; ++i)
  {
    P[0][i] = false;// note: p is guaranteed to have at least 1 row
  }
}

void InitLeftMostColToFalseExceptForP00(Array2D<bool> & P)
{
  for (unsigned i = 1; i < P.mRows; ++i)
  {
    P[i][0] = false;// note: p is guaranteed to have at least 1 col 
  }
}

/*
n = numElements
N = Sum of all elements

S = x1, ... xn
N = sum(S) = x1 + ... + xn

bool p(i,j) = sum(subsetOf{x1, ... xj}) == i;

goal:
  compute p(N/2, n)

recurrence relation:
  p(i,j) = p(i, j-1) || p(i-xj, j-1)
*/

// input: list of integers S
// output: true if S can be partitioned 
//         into 2 subsets that have equal sum
bool FindPartition(const std::vector<int> & S)
{
  unsigned n = S.size();
  int N = std::accumulate(S.begin(), S.end(), 0);

  //table [i, j]
  // i (row) represents the sums
  // j (col) represents the element index

  // first row represents i == 0
  // lastt row represents i == sum / 2

  // first col represents j == 0
  // lastt col represents j == numElements  
  Array2D<bool> P( N / 2 + 1, n + 1);
  InitTopRowToTrue(P);
  InitLeftMostColToFalseExceptForP00(P);
  for (unsigned i = 1; i <= N/2; ++i)
  {
    for (unsigned j = 1; j <= n; ++j)
    {
      P[i][j] = P[i][j - 1] || P[i - S[j - 1]][j - 1];
    }
  }
  return P[N/2][n];
}