YSMull
<-- algorithm



原题链接

2021/04/01

题目描述

带重复元素的全排列。

回溯法

首先对数组进行排序，把重复的元素放到一起，所以这里不能用 swap 来破坏数组的有序性。

每一轮从 arr 中挑选一个元素放到 collector 中参与排列。

有两个条件来约束 arr 中位置 i 的元素是否可以参与排列：

  1. 如果位置 i 的元素已经被使用过了，那么 i 不可以重复参与排列（这个可以过第 46 题，不带重复元素的全排列）。
  2. 如果位置 i 的元素跟 i-1 位置的元素大小一样的，并且 i-1 的元素都没有参与排列，那么 i 也不能参与排列。
impl Solution {
    pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut vis: Vec<bool> = (0..nums.len()).map(|x| false).collect();
        let mut result = vec![];
        nums.sort();
        Solution::permutation_dup(&mut nums, 0, &mut vis, &mut vec![], &mut result);
        return result;
    }

    fn permutation_dup<T: PartialEq + Copy>(arr: &mut Vec<T>, idx: usize, vis: &mut Vec<bool>, collector: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
        if collector.len() == arr.len() {
            res.push(collector.clone());
            return;
        }
        for i in 0..arr.len() {
            if vis[i] || (i > 0 && arr[i] == arr[i - 1] && !vis[i - 1]) {
                continue;
            }
            vis[i] = true;
            collector.push(arr[i]);
            Solution::permutation_dup(arr, idx + 1, vis, collector, res);
            collector.pop();
            vis[i] = false;
        }
    }
}