Avoid code duplication between two functions, but one returns in the middle of the code

Lets say i have two functions inside a class:

vector<int> getAllPossibleNumbers() {
    vector<int> nums;
    for (int i=0; i < MAX; i++)
        if (isAPossibleNumber(i))
            nums.push_back(i);
    return nums;
}

bool hasAtLeastOnePossibleNumber() {
    for (int i=0; i < MAX; ++i)
        if (isAPossibleNumber(i))
            return true;
    return false;
}

I could rewrite the second function as

bool hasAtLeastOnePossibleNumber() {
    return getAllPossibleNumbers().size() > 0;
}

But it's obvious, especially with a very high MAX number, how the first is much more efficent.

So, how can I avoid code duplication of this kind?

I would prefer a general solution, that can work with more complicated functions and can compile with C++11.