class Knapsack
{
public:
  Knapsack (std::vector::const_iterator beg,
      std::vector::const_iterator end,
      int sum)
    : _pieces (beg, end), _sum (sum)
    {
        // precondition: input was sorted
    }
  int UniqueCombinations ();
private:
  std::vector _pieces;
  int _sum;
};
 
// Each combination is counted only once
// Hint: If a pick contains several equal items in a row,
// they were all picked from the front of a run of
// equal items in the (sorted) input (see the skipping below)
int Knapsack::UniqueCombinations ()
{
  int count = 0;
  std::vector::const_iterator it = _pieces.begin ();
  std::vector::const_iterator end = _pieces.end ();
  assert (it != end);    
  do
  {
     int curItem = *it;
     int newSum = _sum - curItem;
     ++it;
     if (newSum == 0)
     {
       ++count;
     }
     else if (newSum > 0 && it != end)
     {
       Knapsack smallerKnapsack (it, end, newSum);
       count += smallerKnapsack.UniqueCombinations ();
     }
     // skip all equal value items
     while (it != end && *it == curItem)
       ++it;
    } while (it != end);
  return count;
}
 
int FillKnapsack (int const * arr, int size, int sum)
{
  if (size == 0)
  {
    std::cout << "0 combinations: empty array" << std::endl;
    return 0;
  }
 
  try
  {
    std::vector data (arr, arr + size);
    // sort in decreasing order
    std::sort (data.begin (), data.end (), std::greater ());
    Knapsack knapsack (data.begin (), data.end (), sum);
    int comb = knapsack.UniqueCombinations ();
 
    std::cout << comb << " combination(s)" << std::endl;
    return comb;
  }
  catch (std::bad_alloc)
  {
    std::cerr << "Out of memory" << std::endl;
  }
  catch (...)
  {
    std::cerr << "Unknown error" << std::endl;
  }
  return 0;
}

// combinations
// how many combinations of k objects can you choose from a set of n objects ?
// this method avoids overflow that you hit with:
//    factorial(n) / (factorial(k) * factorial(n-k))
// see http://www.cs.sjsu.edu/faculty/fecteau/cs140/combPerm.html
unsigned int combinations(unsigned int r, unsigned int n)
  {
  // Assert(n >= k);
  unsigned int k = r < n-r ? r : n-r;
  unsigned int answer = 1;
  unsigned int multiplier = n;
  unsigned int divisor = 1;
  while (divisor <= k)
    {
    answer = ( answer * multiplier ) / divisor; // this will evenly divide 
    multiplier--;
    divisor++;
    }
  return answer;
  }
 
// SumsRecipe
//
// Given a "recipe" for producing a certain sum, tell how many ways that recipe
// can be achieved given the set of numbers indicated by Nums.  Both the recipe
// and the input list are set up so that array[j] tells you how many j's you have
// (or in the case of the recipe, how many j's are needed)
//
unsigned int SumsRecipe(const unsigned int Nums[],
    const unsigned int Recipe[],
    unsigned int Max)
  {
  unsigned int Sums = 1;
  for (unsigned int j = 1; j <= Max; j++)
    {
    if (Nums[j] < Recipe[j])
      return 0;
    if (Recipe[j] != 0)
      Sums *= combinations(Recipe[j], Nums[j]);
    }
  return Sums;
  }
 
// EnumRecipe
//
// Class which provides a somewhat brute-force method of enumerating over all
// the possible "Recipes" for making the value X as a sum of numbers 1-Max.
//
// It really just ticks through the recipes like an odometer, trying:
//   1 one, then 2 ones, then 3 ones...
// When it hits the maximum number of ones you can have it then tries:
//   1 two with 0 ones, then 1 two with 1 one, then 1 two with 2 ones...
//
// Although it might seem like this is a terrible way to generate these
// recipes, there are a couple of "saving graces".  We know
// we don't have more than Length numbers available, and that the total
// can't be greater than X...so if we hit an excess of either of these
// conditions we can fast-forward the "odometer" to the next setting
// which zeroes one of the wheels.
//
class EnumRecipe
  {
private:
  unsigned int m_X; // Target value for our recipe's sum
  unsigned int m_Length; // Most numbers that could occur in a recipe
  unsigned int m_Max; // Maximum value of any given number
  unsigned int m_Used; // Numbers used in this recipe
  unsigned int m_Total; // Current running total sum
  bool m_First; // First time calling the enumerator?
  const unsigned int* m_Nums; // How many of each number is available in the input?
 
public:
  EnumRecipe(unsigned int X,  
      const unsigned int* Nums, 
      unsigned int Length, 
      unsigned int Max) :
    m_X(X),
    m_Nums(Nums),
    m_Length(Length),
    m_Max(Max),
    m_Used(0),
    m_Total(0),
    m_First(true)
    { // Nothing to do
    }
 
  bool NextRecipe(unsigned int Recipe[])
    {
    if (m_First)
      // since this is the first call, start by zeroing out
      // the recipe that the user passed in...
      {
      for (unsigned int j = 0; j <= m_Max; j++)
        Recipe[j] = 0;
      m_First = false;
      // Assert(m_Total == 0);
      // Assert(m_Used == 0);
      }
 
    unsigned int Wheel = 1;
    while (true)
      {
      // Will increasing the current "Wheel" lead to a
      // "Recipe" that uses more values than we have as
      // input, or one that the recipe's summation will 
      // exceed our target X value?
      if ((m_Used < m_Length) && 
          (m_Total < m_X) && 
          (m_Nums[Wheel] >= Recipe[Wheel]))
        {
        Recipe[Wheel]++;
        m_Total += Wheel;
        m_Used++;
 
        if (m_Total == m_X)
          return true;
 
        // as on an odometer, each time we successfully
        // increment one of the wheels, the next wheel
        // we'll try to increment will be the first again
        Wheel = 1;
        }
      else
        // We reached the maximum value for this "wheel"
        {
        // Is it the last one?  If so, we're done.
        if (Wheel == m_Max)
          return false;
 
        // Zero this wheel and update our state variables.
        // This intermediate state is one that we've visited
        // before, so no need to test total against m_X
       m_Total -= (Wheel * Recipe[Wheel]);
       m_Used -= Recipe[Wheel];
       Recipe[Wheel] = 0;
       Wheel++;
        }
      }
 
    return true;
    }
 
  virtual ~EnumRecipe()
    { // Nothing to do
    }
  };
 
// SumsThatAddToXSpecialized
//
// Specialized version of code which answers the "how many ways
// are there to achieve the sum of X using the integers in Values[]".
// This case is specialized because it assumes that the
// values in the array range from 1..Max.  What's different about
// this particular approach is that the performance is not a
// function of the length of the input array.
//
unsigned int SumsThatAddToXSpecialized(
    unsigned int X, 
    const unsigned int Values[], 
    unsigned int Length,
    unsigned int Max)
  {
  unsigned int Nums[Max+1];
  for (unsigned int j = 0; j <= Max; j++)
    Nums[j] = 0;
  for (unsigned int i = 0; i < Length; i++)
    {
    // Assert((Values[i] <= Max) && (Values[i] > 0));
    Nums[Values[i]]++;
    }
 
  unsigned int Sums = 0;
 
  unsigned int Recipe[Max+1];
  EnumRecipe er (X, Nums, Length, Max);
  while (er.NextRecipe(Recipe))
    Sums += SumsRecipe(Nums, Recipe, Max);
 
  return Sums;
  }