Jump game --- a tough case can be passed in Visual C++, but always be TLE in leetcode

Question

error: I can pass the case in the Visual Studio 2010, the case is tough: [25000, ......., 2369], totally 1305 numbers..I can surely pass it and just one recursion(because I jump from the largest number, the first jump is 1304) but the leetcode tells me it's TLE, I really confused, could you help me? thank you~

// the index means the situation where the point is, and 0 -> A[index] means the steps we can jump, we try the step from the largest to the 0.

    class Solution {

    public:
    int flag;
    bool canJump(int A[], int n) {
    flag = 0;//indicator of found of way to jump game, when flag = 1
    int tip[n];
    memset(tip, 1, sizeof(tip));//used for pruning, the initial value is 1
    if(n == 0)
        return false;
    else if(n == 1)
        return true;
    else
    {
        can(A, 0, n, tip);
        if(flag != 0)
            return true;
        else
            return false;
    }
}
void can(int A[], int index, int n, int tip[])
{
    int step;
    int tmp;
    if(flag != 0)//flag !0 means win the jump game, no need to continue to recursion.
        return;
    if(index == n - 1)// means can reach the last point.
    {
        flag++;
        return;
    }
    else
    {
        if(flag != 0)//used for pruning
            return;
        if(A[index] == 0)//can not move any steps, just pruning
            return;
        if(tip[index] == 0)//means the previous try has confirmed that this point can not reach the termination, used for pruning
            return;
        if(A[index] + index >= n)//jump from the largest value, but the largest value maybe larger than the rest of steps, so here we make a pruning, let it not more than the rest of steps.
            step = n - 1 - index;
        else
            step = A[index];
        for(; step >= 1; step--)
        {
            tmp = index;//protect parameter "index", so here I used the copy one
            tmp += step;
            if(A[tmp] == 0 && tmp != n - 1)// if value is 0 and the tmp is not the last point, so just continue next 
                continue;
            if(tmp < n)
            {
                can(A, tmp, n, tip);
                if(flag != 0)// if after the above can(), the flag changed, no need to recursion next
                    break;
            }
            else
                return;
        }
        if(flag == 0)//after all "tmp" validation, we can see whether the point tmp is valid. just for pruning
            tip[tmp] = 0;
        return;
    }
    return;
}

};

Comments

Could you please format your code correctly? The last } is out of your code box.

Answer 1

See comments below.

// C++
class Solution {
    // .....
    if(tmp < n)
    {
        if(tip[tmp]==0) break; // Please do a break here, otherwise your running time will be O(N^2)
        can(A, tmp, n, tip);
        if(flag != 0)
            break;
    }
    // .....
};

Comments

It's amazing, it really works, but I am more confused because of this typical case [25000, .........2369]totally 1305 numbers, my code just run in one recursion(the first step is 1304 and reach the terminate point in the first try and quit the recursion),so I do not know why this is TLE for this typical case? I am looking forward to hear from you~ Thank you very much~

---

The judge will run the test cases all together, so it is not necessary that the last executed input takes too much time. It is possible that the previous cases take too much time and when the judge execute this input, the time is over.