全排列 II

Tips

题目类型: BackTracking

题目

给定一个有重复数字的序列, 按任意顺序返回所有不重复的全排列.

提示:

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

示例

输入: [1, 1, 2]

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

题解

遇到回溯算法, 先把决策树画出来, 我们能发现两条规律, 为了表示两个 1 代表不同的意义, 这里用 1ᵃ 和 1ᵇ 表示:

1. 如果在一条路径上, 一个相同的数字已经被选择过了, 那这条路径需要被废弃掉, 也就是上图红色圆形标注的部分. 比如最左边的 1ᵃ -> 1ᵃ 这条, 抑或是 1ᵃ -> 1ᵇ -> 1ᵃ 这条.

2. 在"同一层", 如果相邻的两个数字相同, 那它们生成的子树一定是相同的, 因此需要过滤掉一个, 也就是上图红色三角形标注的部分. 但要注意的是, 如果同一层一个值已经被用过了, 即便它右边的值与之相等, 右边这个值不会被过滤掉, 比如第二层左侧的 1ᵃ -> 1ᵇ -> 2, 因为 1ᵃ 在第一条规则中已经被剪掉了, 1ᵇ 即便和 1ᵃ 相等, 也不会被剪掉.

在具体实现上, 为保证相邻两个可以正常比较, 需要先对给定数组做一次排序.

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const res = []
  const n = nums.length
  const visited = new Array(n).fill(false)
  nums.sort((a, b) => a - b) // 排序

  const dfs = (track) => {
    if (track.length === n) {
      res.push(track)
      return
    }

    for (let i = 0; i < n; i++) {
      // 对应第二条规则: 相邻两个值相等 && 保证数组不越界 && 保证前一个没被用过
      // 这里用 if (i + 1 < n && !visited[i + 1] && nums[i] === nums[i + 1]) { continue } 也是可以的
      if (nums[i - 1] === nums[i] && i - 1 >= 0 && !visited[i - 1]) {
        continue
      }

      // 对应第一条规则: 这个数使用过了, 跳过
      if (visited[i]) {
        continue
      }

      track.push(nums[i]) // 做选择
      visited[i] = true // 记录路径上做过的选择
      dfs(track.slice()) // 递归
      track.pop() // 撤销选择
      visited[i] = false // 也要撤销一下对它的记录
    }
  }

  dfs([])
  return res
}

Rust

pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums: Vec<i32> = nums;
    nums.sort();

    let mut visited = vec![false; nums.len()];
    let mut res: Vec<Vec<i32>> = vec![];
    dfs(&nums, &mut visited, &mut vec![], &mut res);
    res
}

#[allow(unused)]
fn dfs(nums: &Vec<i32>, visited: &mut Vec<bool>, track: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
    if track.len() == nums.len() {
        res.push(track.to_vec());
        return;
    }

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

        if (visited[i]) {
            continue;
        }

        visited[i] = true;
        track.push(nums[i]);
        dfs(nums, visited, track, res);
        track.pop();
        visited[i] = false;
    }
}