[LeetCode]47.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].

【分析】

这个题跟[LeetCode]46.Permutations非常类似，唯一的区别就是在这个题目中元素集合可以出现重复。这给我们带来一个问题就是如果不对重复元素加以区别，那么类似于{1,1,2}这样的例子我们会有重复结果出现。那么如何避免这种重复呢？方法就是对于重复的元素循环时跳过递归函数的调用，只对第一个未被使用的进行递归，我们那么这一次结果会出现在第一个的递归函数结果中，而后面重复的会被略过。如果第一个重复元素前面的元素还没在当前结果中，那么我们不需要进行递归。想明白了这一点，代码其实很好修改。首先我们要对元素集合排序，从而让重复元素相邻，接下来就是一行代码对于重复元素和前面元素使用情况的判断即可。

【代码】

/*********************************
*   日期：2015-01-19
*   作者：SJF0115
*   题目: 47.Permutations II
*   网址：https://oj.leetcode.com/problems/permutations-ii/
*   结果：AC
*   来源：LeetCode
*   时间复杂度：O(n!)
*   空间复杂度：O(n)
*   博客：
**********************************/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > result;
        if(num.empty()){
            return result;
        }//if
        // 排序
        sort(num.begin(),num.end());
        bool visited[num.size()];
        vector<int> visitedVec;
        // 递归
        DFS(num,visited,visitedVec,result);
        return result;
    }
private:
    void DFS(vector<int> &num,bool visited[],vector<int> &visitedVec,vector<vector<int> > &result){
        // 形成一个全排列
        if(num.size() == visitedVec.size()){
            result.push_back(visitedVec);
            return;
        }//if
        for(int i = 0;i < num.size();++i){
            // 重复元素
            if(i > 0 && !visited[i-1] && num[i] == num[i-1]){
                continue;
            }//if
            // 如果没有访问过
            if(visited[i] == false){
                visited[i] = true;
                visitedVec.push_back(num[i]);
                DFS(num,visited,visitedVec,result);
                visitedVec.pop_back();
                visited[i] = false;
            }//if
        }//for
    }
};

int main(){
    Solution solution;
    vector<int> num;
    num.push_back(1);
    num.push_back(1);
    num.push_back(2);
    // 重新排列
    vector<vector<int> > permutes = solution.permuteUnique(num);
    // 输出
    for(int i = 0;i < permutes.size();i++){
        cout<<"[";
        for(int j = 0;j < permutes[i].size();j++){
            cout<<permutes[i][j];
        }//for
        cout<<"]"<<endl;
    }
    return 0;
}

【代码二】

/*********************************
*   日期：2015-01-19
*   作者：SJF0115
*   题目: 47.Permutations II
*   网址：https://oj.leetcode.com/problems/permutations-ii/
*   结果：AC
*   来源：LeetCode
*   时间复杂度：O(n!)
*   空间复杂度：O(n)
*   博客：
**********************************/
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > result;
        if(num.empty()){
            return result;
        }//if
        int count = num.size();
        // 排序
        sort(num.begin(),num.end());
        // 统计每个元素的个数
        map<int,int> countMap;
        for(int i = 0;i < count;++i){
            countMap[num[i]]++;
        }//for
        // 每个元素和出现次数复合绑定
        vector<pair<int,int> > nums;
        pair<int,int> pair;
        for(int i = 0;i < count;++i){
            pair.first = num[i];
            pair.second = countMap[num[i]];
            nums.push_back(pair);
        }//for
        vector<int> visited;
        // 递归
        DFS(nums,visited,result);
        return result;
    }
private:
    void DFS(vector<pair<int,int> > &nums,vector<int> &visited,vector<vector<int> > &result){
        // 形成一个全排列
        if(nums.size() == visited.size()){
            result.push_back(visited);
            return;
        }//if
        int numCount = nums.size();
        for(int i = 0;i < numCount;++i){
            int count = 0;
            // 重复元素不能重复打头
            if(i > 0 && nums[i].first == nums[i-1].first){
                continue;
            }//if

            int countVisit = visited.size();
            // 统计重复元素已访问的个数
            for(int j = 0;j < countVisit;++j){
                if(visited[j] == nums[i].first){
                    count++;
                }//if
            }//for
            // 如果还有元素没有访问过
            if(count < nums[i].second){
                visited.push_back(nums[i].first);
                DFS(nums,visited,result);
                visited.pop_back();
            }//if
        }//for
    }
};

int main(){
    Solution solution;
    vector<int> num;
    num.push_back(1);
    num.push_back(2);
    num.push_back(1);
    // 重新排列
    vector<vector<int> > permutes = solution.permuteUnique(num);
    // 输出
    for(int i = 0;i < permutes.size();i++){
        cout<<"[";
        for(int j = 0;j < permutes[i].size();j++){
            cout<<permutes[i][j];
        }//for
        cout<<"]"<<endl;
    }
    return 0;
}