Here is a recursive solution - ill post the code, then explain what is going on. Also, this is code I wrote for brute forcing a knapsack cipher, so there is a little more going on then is necessary to understand (the whole set bit business.)

```
int set_bit(int solution, int bit)
{
int a = (1 << bit);
return (solution+a);
}
//the int returned by subset sum has the bit values set to the solution
// if -1, there was no solution
int subset_sum(int s, int a_index, int solution)
{
//to do - make bits work right
//we need a successful add to make bits on the left side
if (s <0)
return -1;
if (s == 0)
return solution;
if (a_index == 16)
return -1;
int included = subset_sum( s - hard[a_index], a_index+1, set_bit(solution, a_index) );
int not_included = subset_sum( s - hard[a_index], a_index+1, solution );
if (included >= 0)
return included;
return not_included;
}
```

**explanation time:

The subset_sum function takes a target sum and the current place in our array, a_index. the solution to the subset sum problem is:

1) include the current item in our solution - the solution is the sum minus the current item, plus the solution to the rest of the array.

2) do not include the current item in our solution - the solution is the solution to the sum and rest of the array

base cases: we included an item that made the sum negative, return -1

we ran out of array ...