DFS+剪枝去重+排序+回溯算法+DFS遍历叶子节点 47. 全排列 II

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题
难点：数组中有相同元素，但输出的全排列数组不能有相同的排列；

需要对每次的dfs算法进行剪枝！

去重剪枝需要先排序，然后遍历时跳过相同元素，进行剪枝！

解法

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());              //先排序+跳过除重
        visited.resize(nums.size(),false);
        dfs(nums.size(),nums);
        return result;
    }

private:
    vector<vector<int>> result;
    vector<int> path;
    vector<bool>visited;
    void dfs(int n,vector<int> &nums)
    {
        if(path.size()==n)
        {
            result.push_back(path);
            return;
        }

        for(int i=0;i<n;i++)
        {
            if(visited[i]) continue;
            if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;
            visited[i]=1;
            path.push_back(nums[i]);
            dfs(n,nums);
            visited[i]=0;
            path.pop_back();
        }
    }
};

注意点
去重行如下，在for循环中多加了一行；

  if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;

当执行该行时，说明当前遍历的i与i-1的值相等，而且i-1已经完成遍历，故此次path要添加数字的位置已经添加过该值，无需重复添加，跳过即可；
（相同元素相邻放置是这个去重的关键，所以需要先对nums排序）；

稍微改变

	  if(i>0&&nums[i]==nums[i-1]&&visited[i-1]) continue;

去掉visited[i-1]前面的感叹号，程序也能得到正确答案；
当有3个以上相等元素时，取前两个元素，都取不到后一个元素，故dfs会完全执行后失败返回，浪费很多时间，直到最先取相同元素的最后一个时，且逐个往前取相同元素时，会成功返回一个解，故此写法复杂度远远大于上面的写法；

总结
重复答案的 去重+剪枝 考虑先排序，后在遍历的合适时间跳过相同元素，完成剪枝去重；

最后

以上就是昏睡超短裙为你收集整理的DFS+剪枝去重+排序+回溯算法+DFS遍历叶子节点 47. 全排列 II的全部内容，希望文章能够帮你解决DFS+剪枝去重+排序+回溯算法+DFS遍历叶子节点 47. 全排列 II所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。