首页 > 代码库 > Leetcode--permutations II

Leetcode--permutations II

Problem Description:

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

分析:题目意思是打印有重复数字的所有排列,可以利用一个判断函数随时判断前面是否已经出现过,出现过则不再进行排列。具体代码如下:

class Solution {
public:
    

    void swap(int &a,int &b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    
    bool Isduplicate(vector<int> num,int begin,int last)
    {
        for(vector<int>::size_type i=begin;i!=last;++i)
            if(num[i]==num[last])
                return false;
        return true;
    }
    
    
    void permutations(vector<int> num,int begin,vector<int> &permutation,vector<vector<int> > &res)
    {
        if(begin==num.size())
        {
            res.push_back(permutation);
            return;
        }
        
        for(vector<int>::size_type index=begin;index!=num.size();++index)
        {
            
            if(Isduplicate(num,begin,index))
            {
            swap(num[begin],num[index]);
            permutation.push_back(num[begin]);
            permutations(num,begin+1,permutation,res);
            permutation.pop_back();
            swap(num[begin],num[index]);
            }
            
        }
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        if(num.empty())
            return res;
        vector<int> permutation;
        permutations(num,0,permutation,res);
        return res;
    }
};



Leetcode--permutations II