跳至主要內容

47, 全排列II

Mike大约 2 分钟backtrackingmediumarraybacktracking

一、题目描述

给定一个可包含重复数字的序列nums,按任意顺序返回所有不重复的全排列。

示例 1
输入: nums = [1, 1, 2]
输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

示例 2
输入: nums = [1, 2, 3]
输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

提示

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

相关主题

  • 数组
  • 回溯

二、题解

方法 1: 回溯

pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort_unstable();
    const DFS: fn(&mut Vec<i32>, &mut Vec<i32>, &mut Vec<Vec<i32>>) = 
        |nums, permute, res| {
            if permute.len() == nums.len() {
                res.push(permute.clone());
                return;
            }

            for i in 0..nums.len() {
                if nums[i] == i32::MIN {
                    continue;
                }
                if i > 0 && nums[i] == nums[i - 1] {
                    continue;
                }

                permute.push(nums[i]);
                nums[i] = i32::MIN;

                DFS(nums, permute, res);

                nums[i] = permute.pop().unwrap_or_default();
            }
        };
    let mut res = vec![];

    DFS(&mut nums, &mut vec![], &mut res);

    res
}

方法 2: 递归

pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort_unstable();

    const DFS: fn(Vec<i32>) -> Vec<Vec<i32>> = |nums| {
        let mut res = vec![];

        if nums.len() <= 1 {
            res.push(nums);
            return res;
        }

        for i in 0..nums.len() {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            let num = nums[i];
            let new_nums = nums
                .iter()
                .enumerate()
                .filter_map(|(idx, &val)| if idx == i { None } else { Some(val) })
                .collect::<Vec<_>>();

            let perms = DFS(new_nums);
            for mut perm in perms {
                perm.push(num);
                res.push(perm);
            }
        }
        res
    };

    DFS(nums)
}