leetcode：Permutations II （序列全部无重复排列）【面试算法题】

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

题意输出给定序列的所有无重复排列。

做法和思路基本和上道题一样。

不同的地方有两点。

1.先对num排序，这样重复的元素就是相邻的。

2.dfs中的for循环里，当遍历了num的一个值时，跳过num相同的值，防止重复遍历。

这个样处理，结果就是无重复排列的。

class Solution {
private:
    vector<vector<int> >result; 
    int data[10];
    int sign[10];
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        result.clear();
        sort(num.begin(),num.end());
        memset(sign,0,sizeof(sign));
        int n=num.size();
        dfs(n,0,num);
        return result;
    }
    void dfs(int n,int index,vector<int> &num)
    {
        if(index==n)
        {
            vector<int >t;
            for(int i=0;i<n;++i)t.push_back(num[data[i]]);
            result.push_back(t);
            return;
        }
        for(int i=0;i<n;++i)
        {
            if(sign[i]==0)
            {
                sign[i]=1;
                data[index]=i;
                dfs(n,index+1,num);
                sign[i]=0;
                while(i<n-1&&num[i+1]==num[i])++i;
            }
        }
    }
};
// http://blog.****.net/havenoidea