LeetCode 47. 全排列 II

作者:Choi Yang

更新于:7 个月前

字数统计:653 字

阅读时长:3 分钟

题目描述

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

示例:

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

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

解题思路

本题是求全排列，并且排列不能重复。我们用一个 vis数组维护一下，让每一条路线保证不重复选取元素，而对于每一层而言，需要判断相邻元素是否相同，相同的就没必要走了，例如下图中红色三角形部分。

如果当前的选项 nums[i] ，与同一层的上一个选项 nums[i - 1] 相同，且 nums[i - 1]有意义（即索引 >= 0），且没有被使用过，那就跳过该选项。

因为 nums[i - 1]如果被使用过，它会被修剪掉，不是一个选项了，即便它和 nums[i]重复，nums[i]还是可以选的。

参考 xiao_ben_zhu 大佬题解

javascript

var permuteUnique = function (nums) {
  let res = [];
  nums.sort((a, b) => a - b);
  let vis = {};
  let dfs = (t) => {
    if (t.length === nums.length) {
      res.push(t);
    }
    for (let i = 0; i < nums.length; i++) {
      if (i - 1 >= 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
      if (vis[i]) continue;
      vis[i] = true;
      t.push(nums[i]);
      dfs(t.slice(), i + 1);
      t.pop();
      vis[i] = false;
    }
  };
  dfs([], 0);
  return res;
};

cpp

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> vis(nums.size(), 0);
        vector<int> t;
        sort(nums.begin(), nums.end());
        function<void(int)> dfs = <CustomLink title="&" href="int u" /> {
            if (t.size() == nums.size()) {
                res.push_back(t);
                return;
            }
            for (int i = u; i < nums.size(); i++) {
                if (i - 1 >= 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
                if (vis[i]) continue;
                vis[i] = true;
                t.push_back(nums[i]);
                dfs(0);
                t.pop_back();
                vis[i] = false;
            }
        };
        dfs(0);
        return res;
    }
};

java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> t = new ArrayList<>();
        boolean[] vis = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, res, t, vis, 0);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, List<Integer> t, boolean[] vis, int u) {
        if (u == nums.length) {
            res.add(new ArrayList<>(t));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i - 1 >= 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
            if (vis[i]) continue;
            vis[i] = true;
            t.add(nums[i]);
            dfs(nums, res, t, vis, u + 1);
            t.remove(t.size() - 1);
            vis[i] = false;
        }
    }
}

python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        vis = [False] * len(nums)
        nums.sort()
        def dfs(t, u):
            if u == len(nums):
                res.append(t[:])
                return
            for i in range(len(nums)):
                if i - 1 >= 0 and nums[i] == nums[i - 1] and not vis[i - 1]:
                    continue
                if vis[i]:
                    continue
                vis[i] = True
                t.append(nums[i])
                dfs(t, u + 1)
                t.pop()
                vis[i] = False
        dfs([], 0)
        return res

学如逆水行舟，不进则退

Contributors

Choi Yang