47. Permutations II (Back-Track, Sort)

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].

思路：有重复数字的情况，之前在Subsets II，我们采取的是在某一个递归内，用for循环处理所有重复数字。这里当然可以将数组排序，然后使用该方法。

而另一种方法是不排序，在一个递归内申请一个set，用来判断该数字是否已经在当前depth出现过：如果nums[depth]出现过，那么说明这个前缀在之前的遍历已存在，不需要再进行讨论。

class Solution {

public:

    vector<vector<int> > permuteUnique(vector<int> &num) {

        result.clear();

        dfs(num, );

        return result;

    }

    void dfs(vector<int> num, int depth)

    {

        if(depth == num.size()-)

        {

            result.push_back(num);

            return;

        }

        dfs(num,depth+);

        set<int> flag; //用来判断当前数字是否在depth位置出现过

        flag.insert(num[depth]);

        int temp = num[depth];

        for(int i = depth+; i< num.size(); i++)

        {

           if(flag.find(num[i])!=flag.end()) continue;

           flag.insert(num[i]);

           num[depth]=num[i];

           num[i] = temp;

           dfs(num,depth+);

           num[i]=num[depth];

           num[depth]=num[i];

        }

    }

private:

    vector<vector<int> >  result;

};

思路II：同样可以用insertion sort的方法

碰到相同元素，break for循环。注意不是continue，因为假设要插入的元素nums[i]与result[resultIndex][k]相同，那么这个result[resultIndex][k]已经在上一轮的时候，对{0...k-1}的位置已经做过插入排序。如果再进行插入，会造成相同的前缀，导致重复result。

class Solution {

public:

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        int size = nums.size();

        int resultSize;

        int resultIndex;

        int count;

        vector<vector<int>> result;

        vector<int> resultItem(,nums[]);

        result.push_back(resultItem);

        for(int i = ; i <size; i++){ //nums[i] is the num to insert

            resultSize = result.size(); //resultSize in the preceeding insert iterate

            for(int j = ; j < resultSize; j++){ //iterate the array to do insertion

                result[j].push_back(nums[i]);

                resultIndex = j;

                for(int k = i-; k >=; k--){ //like insertion sort, adjust forward

                    if(nums[i]==result[resultIndex][k]) break; //equal element, don't insert

                    result.push_back(result[resultIndex]);

                    result[result.size()-][k+] = result[resultIndex][k];

                    result[result.size()-][k] = result[resultIndex][k+];

                    resultIndex = result.size()-;

                }

            }

        }

        return result;

    }

};

巴特西

47. Permutations II (Back-Track, Sort)

最新文章

热门文章