可视化图解算法55：有重复项数字的全排列

原创

用户11589437

修改于 2025-07-11 10:49:24

16200

代码可运行

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

运行总次数：0

代码可运行

牛客网面试笔试TOP101 | LeetCode 47. 全排列 II

1. 题目

描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： 0 <n≤8 ，数组中的值满足 -1 ≤val≤5

要求：空间复杂度 O(n!)，时间复杂度 O(n!)

示例1

输入：

[1,1,2]

返回值：

[[1,1,2],[1,2,1],[2,1,1]]

示例2

输入：

[0,1]

返回值：

[[0,1],[1,0]]

2. 解题思路

通过回溯法实现数字项的全排列，要特别留意重复数字的处理。具体思路如下：

参考回溯算法模板，进行以下操作：

遍历每一个元素，以该元素作为开头的数字数列。首先选取该数字，并标记该数字已经使用过；再递归选择其他数字；撤销该数字，让其他数字作为开头。缩小数字区间：该元素已经使用过；当前元素与前一个元素一样，且前一个已经使用过。

递归终止条件：选择的数字已经达到n个（数列的长度），则保存选择数字组成的序列，并返回。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

B站 @好易学数据结构

3. 编码实现

核心代码如下：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param num int整型一维数组
 * @return int整型二维数组
 */
func permuteUnique(num []int) [][]int {
  // write code here
  result = make([][]int, 0)
  path = make([]int, 0)
  mark = make([]bool, len(num))
  sort.Ints(num)
  backtracking(num)
  return result
}

func backtracking(num []int) {
  // 2.递归终止条件：已经找到一条路径（路径数组满了）,则加入到输出列表
  if len(path) == len(num) {
    //2.1 存放结果
    tmp := append([]int{}, path...) //新建一个切片，如果是引用原来切片，是地址引用，path内容改变时，result数据也会发生改变
    result = append(result, tmp)
    //2.2 返回
    return
  }

  //1.选择：在本层集合中遍历元素
  for i := 0; i < len(num); i++ {
    //1.4 剪枝
    //1.4.1 元素已经使用过则不需要再加入了
    if mark[i] {
      continue
    }
    //1.4.2 当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过
    if (i >= 1) && (num[i-1] == num[i]) && mark[i-1] {
      continue
    }

    //1.1 处理节点 （选取数字）
    path = append(path, num[i])
    mark[i] = true
    // 1.2 递归（选择其他数字）
    backtracking(num)
    //1.3 回溯，撤销选择
    path = path[:len(path)-1]
    mark[i] = false
  }
}

var (
  result [][]int //结果集
  path   []int   //路径
  mark   []bool
)

具体Go、Java、Python 完整代码你可以参考下面视频的详细讲解。

B站 @好易学数据结构