[LeetCode] Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

这道题很容易出现Time Limit Exceeded！

分析：

输入：[1,1,0,0,1,-1,-1,1]，将会有650条答案，但分析一下这里面一开始就有很多重复的，所以对于bfs的思想在求解的过程中要去掉多余的基数，后面才会少费时间。

方法1：把下标存到te中，然后变回本身的数字Time Limit Exceeded！

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > result,temp2;
        int len = num.size();
        //先给tempRes里存num的下标
        vector<int> te,temp;
        for(int i=0;i<len;i++){
            if(find(temp.begin(),temp.end(),num[i])==temp.end()){
               temp.push_back(num[i]);
               te.push_back(i);
               temp2.push_back(te);
               te.clear();
            
            }
            
        }//end for

        while(!temp2.empty()){
            te  = temp2.back();
            temp2.pop_back();

            if(te.size() == len){
               for(int i=0;i<len;i++){
                  te[i] = num[te[i]];
                }
               if(find(result.begin(),result.end(),te)==result.end())
                  result.push_back(te);
               continue;
            }

            for(int i=0;i<len;i++){
                if(find(te.begin(),te.end(),i)==te.end()){
                    te.push_back(i);
                    temp2.push_back(te);
                    te.pop_back();
                }
            }
        }//end while

       return result;
    }
};

方法2：与上面方法一模一样，只不过求解过程中把多余的vector及时去掉了。Accept!