Adding Two Lines to Permutation I, Why got Output Limit Exceed?


  • 0
    T

    Based on this solution of permutation I: https://oj.leetcode.com/discuss/18212/my-elegant-recursive-c-solution-with-inline-explanation

    I added if(i!=begin&&num[i]==num[begin])continue; in order to skip the duplicate results. I'm wondering if it will success since OJ gave me Output Limit while my xCode IDE can return right results for several test cases. If not, what is the counter example?

    Below is my code and anyone know where I go wrong? Thanks a lot.

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;;
        if(num.empty())
            return res;
        helper(num, 0, res);
        return res;
    }
    //0...begin-1 is already permutated
    void helper(vector<int> &num, int begin, vector<vector<int> > &res)
    {
        if(begin == num.size())
        {
            res.push_back(num);
            return;
        }
        for(int i = begin; i<num.size(); ++i)
        {
            if(i!=begin&&num[i]==num[begin])//if equal, then [begin+1,n] would have same permutation, so skip
                continue;
            swap(num[i], num[begin]);
            helper(num, begin+1, res);
            swap(num[i], num[begin]);
        }
    }

  • 0
    T

    (2,1,1) may fail my code.


  • 0
    W

    try the case {1,2,1,2,1}, you will find duplicate result.


  • 2
    H

    First, the test case might be unsorted, and you need to sort the list first in order for the line you added to work;

    Second, even if the original list is sorted, the list might not be sorted starting from "begin+1" anymore when you recursively call your function after num[i] is swapped to "begin" in your code.

    I posted a modified version here: https://oj.leetcode.com/discuss/20879/sharing-short-solution-using-dfs-modified-from-permutation


  • 0
    H

    why the case must be sorted?


  • 1
    Z

    First sort the original list.

    Second (which I confused for a while), you should not do the second swap to recover. Because this will cause you next list not be sorted. (this is what different from Permutations I, actually, the second swap is also useless in Permutations I since we will always generate all permutations of the sublists, the the recovering process is needless.)


  • 0
    J

    Hi zjh08177, Can you explain what is the reason for your second point? It was confused me. I get stuck it here. Thanks.


Log in to reply
 

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