题目地址(47. 全排列 II)

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

题目描述

  1. 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
  5. 示例 1：
  7. 输入：nums = [1,1,2]
  8. 输出：
  9. [[1,1,2],
  10.  [1,2,1],
  11.  [2,1,1]]
  14. 示例 2：
  16. 输入：nums = [1,2,3]
  17. 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  22. 提示：
  24. 1 <= nums.length <= 8
  25. -10 <= nums[i] <= 10

前置知识


公司

  • 暂无

思路

这道题目和46.全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。
这里又涉及到去重了。
在40.组合总和I、90.子集II 我们分别详细讲解了组合问题和子集问题如何去重。
那么排列问题其实也是一样的套路。
还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
image.png
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

关键点


代码

  • 语言支持：Java

Java Code:

class Solution {
        ArrayList<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        //记录哪些数字被使用过了
        boolean[] used;
        public List<List<Integer>> permute(int[] nums) {
            //排序 使相等的数据放在一起
            Arrays.sort(nums);
            used = new boolean[nums.length];
            loop(nums);
            return res;
        }

        void loop(int[] nums) {
            //终止条件 当路径的数组大小等于初始的数组大小说明遍历到叶子结点了
            if (path.size() == nums.length) {
                res.add(new ArrayList<>(path));
                return;
            }
            //每一层都循环初始数组的大小 因为[1,2] 和[2,1]是都需要的 所以不需要startIndex
            for (int i = 0; i < nums.length; i++) {
                //同子集二 如果遇到的值和上一个值相等 并且他的used还是false 说明他们是在同一层 相等的数据 反之则是子树的相同数据
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                    continue;
                }
                //当遇到从根节点到当前节点使用过的数字的时候 跳过当次循环
                //比如[1,2,2] used[f,f,f] 循环使用过1 used[t,f,f] 这样1就不会碰到它本身了
                if (!used[i]) {
                    //使用过的数字加到path里 并且使当前的used数组对应的位置标记为已使用
                    path.add(nums[i]);
                    used[i] = true;
                    loop(nums);
                    //回溯 使used数组对应的位置标记为未使用
                    used[i] = false;
                    path.removeLast();
                }

            }
        }
    }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：47. 全排列 II - 图2#card=math&code=O%28n%29&id=isQoV)
  • 空间复杂度：47. 全排列 II - 图3#card=math&code=O%28n%29&id=UF8Hx)