Why it got Output Limit Exceeded? Help me!


  • 1
    U
        void helper(vector<int> &num, int start, vector<vector<int> > &result) {
        if (start == num.size() - 1) {
            result.push_back(num);
            return;
        }
        for(int k = start; k < num.size(); ++k) {
            if (start == k || num[start] != num[k]){
                swap(num[start], num[k]);
                helper(num, start + 1, result);
                swap(num[start], num[k]);
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> > result;
        helper(num, 0, result);
        return result;
    }
    

    Above is my code. It got a Output Limit Exceeded. However, if I changed like this

        void helper(vector<int> num, int start, vector<vector<int> > &result) {
        if (start == num.size() - 1) {
            result.push_back(num);
            return;
        }
        for(int k = start; k < num.size(); ++k) {
            if (start == k || num[start] != num[k]){
                swap(num[start], num[k]);
                helper(num, start + 1, result);                
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> > result;
        helper(num, 0, result);
        return result;
    }
    

    It accepted!
    The two algorithms are the same. I got same outputs on my local machine. But using reference and swap back the elements is better for space. I cannot figure out why. NEED HELP.


  • 0
    D

    your code doesn't output unique permutations for input like {1,1,2,2}


  • 0
    U

    Yes. You are right. But could you tell me why the modified code works correctly? Does it send a copy of num when doing the recursive call?


  • 0
    P

    As per my understanding , even your second code should not work. Not sure, how it got accepted.


  • 0
    U

    Can you give me a input example for the second, or the reason why you think it cannot work?


  • 0
    U

    The second code got passed might simply because it could pass all OJ test case. I don't know if it is correct or not.


Log in to reply
 

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