Why TLE on a test case of a very big size vector?


  • 0
    J

    I feel my algorithm is just a standard one as others provided, but why it is TLE? Thanks.

    class Solution {
    public:
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {
            vector<vector<int>> vecs;
            if(num.empty()) {
                return vecs;
            }
            sort(num.begin(), num.end());//ifmissing this, TLE
            vector<int> vec;
            helper(num, target, vecs, vec, 0);
            return vecs;
        }
        void helper(vector<int> &num, int target, vector<vector<int>> vecs, vector<int> &vec, int index) {
            if(target ==0) {
                vecs.push_back(vec);
            } else if(target<0) {
                return;
            } else {
                for(int i=index; i<num.size()&&target-num[index]>=0; ++i) {
                    if(i>index&&num[i]==num[i-1]) {
                        continue;
                    }
                    vec.push_back(num[index]);
                    helper(num, target-num[index], vecs, vec, index+1);
                    vec.pop_back();
                }
            }
        }
    };

  • 0
    J

    failing test case is:
    Time Limit Exceeded

    Last executed input: [29,19,14,33,11,5,9,23,23,33,12,9,25,25,12,21,14,11,20,30,17,19,5,6,6,5,5,11,12,25,31,28,31,33,27,7,33,31,17,13,21,24,17,12,6,16,20,16,22,5], 28


  • 0
    L

    do the filter first, then you will get accepted.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.