0047._Permutations_II.md

47. Permutations II

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/permutations-ii/

内容描述

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

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路1 - 时间复杂度: O(n!nlgn)- 空间复杂度: O(n)*****

和前面的那道题有点类似，可以参考之前的解法。由于做了之前的题目，我直接就用set去重了，虽然通过了，但是时间复杂度比较高，因此需要进行优化

class Solution {
public:
    void DFS(int* visited,vector<int>& nums,set<vector<int> >& ans,vector<int> temp)
    {
         int count1 = 0;
    for(int i = 0;i < nums.size();++i)
        if(!visited[i])
        {
            temp.push_back(nums[i]);
            visited[i] = 1;
            DFS(visited,nums,ans,temp);
            temp.pop_back();
            visited[i] = 0;
            count1 = 1;
        }
    if(!count1)
        ans.insert(temp);
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
               vector<vector<int> > ans;
        int visited[nums.size()];
        memset(visited,0,sizeof(visited));
        set<vector<int> > s;
        vector<int> temp;
        for(int i = 0; i < nums.size();++i)
        {
            visited[i] = 1;
            temp.push_back(nums[i]);
            DFS(visited,nums,s,temp);
            temp.pop_back();
            visited[i] = 0;
        }
        for(auto pos = s.begin();pos != s.end();++pos)
            ans.push_back(*pos);
        return ans;
    }
};

思路2 - 时间复杂度: O(n!)- 空间复杂度: O(n)******

有了之前那道题的经验。我们也可以通过DFS的方法去解，但是有个问题，有相同的数字就会产生重复。因此先对数组进行排序，这样相同的数字就会出现在一起，然后进行DFS时，由于我们是从左往右进行的，因此当一个数与之前的数相等并且之前的数字已经搜索过了，那么我们就不必再搜索这个数。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        vector<int> visited(n, 0), arr;
        dfs(nums, ret, arr, visited);
        return ret;
    }
    void dfs(vector<int>& nums, vector<vector<int>>& ret, vector<int>& arr, vector<int>& visited) {
        if (arr.size() == nums.size()) {
            ret.push_back(arr);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i]) {continue;}
            if (i -1 >= 0 && nums[i] == nums[i-1] && !visited[i-1]) {continue;}
            arr.push_back(nums[i]);
            visited[i] = 1;
            dfs(nums, ret, arr, visited);
            arr.pop_back();
            visited[i] = 0;
        }
    }
};