Count Scorecards challenge problem related to partition number theory

I am having a challenge problem. I have solved the problem but my solution is slow.

The problem is basically the distribution of scores among players. e.g for a 2 player game the possible scorecards combination is 2 because either player can win \$\{0,1\}\$ or \$\{1,0\}\$ while for a 3 player game the possible scorecards combination is 7: \$\{1,1,1\}\$, \$\{0,1,2\}\$, \$\{0,2,1\}\$, \$\{1,0,2\}\$, \$\{1,2,0\}\$, \$\{2,0,1\}\$, \$\{2,1,0\}\$ as a single player can win maximum by 2 other players and minimum by no one.

As I can guess the reason my code is slow is because I am trying to find all valid scorecards and displaying the number.

-
In my first attempt I tried to find all possible combination of scorecards and storing them in a vector, then removing the invalid combinations. This approach was slow.

-
In my second attempt I applied some checks such as that in a series no 2 players can have a score of \$0\$ i.e \$\{0,0,...\}\$ etc cause it is logically not possible. Because if a player doesn't win from any other player then all other player must have won from that particular player so every other player will have at least 1 win. It reduced my calculations by almost 50-60% but it is still slow.

I think my code/logic can be improved: instead of finding all valid combinations, I may find the number of valid combinations with some kind of formula.

```
#include
#include
#include
#include
#include
using namespace std;

bool hasElement(vector& arr, const int& element)
{
vector::iterator found = find(arr.begin(), arr.end(), element);
if (found != arr.end())
return true;
return false;
}

int sumElements(const vector& arr)
{
int s = accumulate(arr.begin(), arr.end(), 0);
return s;
}

bool isPossible(vector& arr, const int& sum, const int& nMax)
{
if (hasElement(arr, -1) || *max_element(arr.begin(), arr.end()) > nMax)
return false;
int s = sumElements(arr);
if (s == sum)
return true;
return false;
}

in

Some more comments.

-
The function rangeSum() can be optimized to:

int rangeSum(int start, int end)
{
  return start*(start-1)/2 + end*(end-1)/2 - 2;
}

which is much better since it's O(1) and not O(n).

-
The function hasElement() can be reimplemented to:

template
inline bool hasElement(const vector& vec, T elem)
{
  return std::find(vec.begin(), vec.end(), elem) != vec.end();
}

-
Assuming you can use C++0x, missing() can be reimplemented to:

template
inline std::size_t missing(const std::vector& tmp)
{
  return std::count_if(tmp.begin(), tmp.end(), [](T elem) {
    return elem == -1;
  });
}

-
The variables maxMax and size aren't used globally. Just declare them locally.

-
You might think of using a functor FindNum – something like:

struct FindNum
{
  void operator()(int i, int max, int rSum, int mZero, int mMax)
  {
    /* … */
  }

  int maxSum, n, maxAllowed, range;
  std::vector tempVec;
  std::vector> mainVec;
};

You really shouldn't use global variables.

StackExchange Code Review Q#9227, answer score: 6