LeetCode 47. 全排列 II:排序 + 回溯剪枝去重的多语言解法详解

原创2026-10-15 23:31:151,756 阅读
文章标签:教程示例工程教育

LeetCode 47. 全排列 II:排序 + 回溯剪枝去重的多语言解法详解

本文以 doocs/leetcode 仓库中 0047.Permutations II 题解 为主体,系统讲解"可含重复数字的序列如何生成不重复全排列"这一经典回溯问题:先排序让重复数字相邻,再通过一条剪枝条件让"同一层中每种值只被选择一次",从而在搜索源头去掉重复分支。读完本文,你将掌握该题的标准解法框架、去重条件的底层语义、完整的复杂度分析,以及 Python3 / Java / C++ / Go / TypeScript / Rust / JavaScript / C# 八种语言的仓库级实现。

一、题目与约束

题目要求:给定一个可能包含重复数字的序列 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

从仓库中该题目录的元信息(README.md 的 front matter)可以看到,本题的标签为:数组、回溯、排序。这正是解题路径的浓缩——"数组"是输入形态,"排序"是去重的前置手段,"回溯"是穷举所有排列的算法骨架。

与上一题 46. 全排列 相比,本题唯一但关键的差异在于:nums 中允许出现重复数字,因此朴素回溯会产出大量重复排列,必须引入去重机制。46 题中 nums 的所有整数互不相同,直接 DFS 即可;47 题在此基础上增加了一条剪枝条件。

二、思路演进:为什么不能直接"回溯 + 集合去重"

最直觉的做法是把 46 题的回溯原封不动搬过来,最后用集合(set)把重复排列过滤掉。从算法正确性上讲这没有问题,但存在明显的效率缺陷:

  • 当 n <= 8 且数组中存在相同数字时,整个子树会被复制多份。例如 [1,1,2] 中两个 1 在回溯树中会各自展开一遍,产生重复的搜索分支;
  • 事后去重既慢又费空间:重复结果先生成、再被丢弃,白白消耗时间与内存。

原文档的"思考"部分点明了问题的本质:

两个相同的数在同一层交换顺序,得到的仍是同一个排列。因此相同值在同一层只应被选择一次。

基于这一观察,正确的做法是:先排序让相等的数相邻,再在同一层跳过"前一个相同值尚未使用"的情况。这样每个位置上每种值只展开一次,生成的所有排列天然不重复,无需事后过滤。

三、排序 + 回溯:核心算法

算法分为两步:

  1. 预处理:对 nums 升序排序。排序后,所有相等的数字都聚拢在相邻位置,为去重剪枝创造条件。
  2. 回溯:设计递归函数 dfs(i),表示当前需要填写第 i 个位置的数。具体逻辑:
    • 若 i == n(n 为数组长度),说明所有位置已填完,将当前排列加入答案数组并返回;
    • 否则枚举 j ∈ [0, n-1],将 nums[j] 填入第 i 个位置。要求 nums[j] 未被使用,并且与前面枚举到的数不重复,这样才能保证当前排列不重复;满足条件后递归调用 dfs(i + 1) 填写下一个位置,递归返回后撤销标记(回溯)。

3.1 去重剪枝条件的语义

整个算法的灵魂在于循环开头的那条剪枝语句,例如 Python 版本:

if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
    continue

它由三个子条件组成,依次判断:

子条件 含义
vis[j] nums[j] 已经在当前排列的前面位置被使用,不能再选
nums[j] == nums[j - 1] 当前候选与前一个候选值相等(因已排序,相等的值必然相邻)
not vis[j - 1] 前一个相同值尚未被使用

当三者同时成立时跳过 nums[j]。可以这样理解:在排好序的数组中,一组相等值(如两个 1)中,只有"最靠左的那个可用副本"才有资格被放到当前层。一旦前一个相等值还没被用过,后面的相等副本一律跳过,于是"同一种值在同一层只会被选择一次",重复分支在源头就被剪掉了。

需要说明的是,这种"剪左留右"与镜像写法"vis[j - 1](剪右留左)"在逻辑上是等价的,都能保证去重;本仓库统一采用 !vis[j - 1] 这种"前一个相同值尚未使用则跳过"的形式,它保证相等元素在排列中始终按原始顺序被选中,语义更直观。

3.2 手推一遍 [1,1,2]

以 nums = [1,1,2](排序后下标 0、1、2 分别为 1,1,2)为例,走一遍递归主路径:

  1. dfs(0):j=0 选 1 填入第 0 位,递归 dfs(1);
  2. dfs(1):j=0 已被使用跳过;j=1 因 nums[1] == nums[0] 且 !vis[0] 不成立(vis[0] 为 true)而允许选择,填入第 1 位得到 [1,1,_];dfs(2) 中 j=2 选 2,得排列 [1,1,2];
  3. 回溯后 dfs(1) 继续 j=2 选 2,dfs(2) 中选 1,得排列 [1,2,1];
  4. 回到 dfs(0):j=1 时 nums[1] == nums[0] 且 !vis[0] 为 true,被剪枝跳过——这正是两个 1 的重复分支被消除的关键;
  5. j=2 选 2 填入第 0 位,后续依次选两个 1,得排列 [2,1,1]。

最终只输出 [[1,1,2],[1,2,1],[2,1,1]] 三个不重复排列,与题目示例完全一致。

四、多语言实现

仓库在 solution/0000-0099/0047.Permutations II/ 目录下为每种语言提供了独立源码文件(Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs),以下代码与 README.md 及对应 Solution.* 文件完全一致。

4.1 Python3

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == n:
                ans.append(t[:])
                return
            for j in range(n):
                if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
                    continue
                t[i] = nums[j]
                vis[j] = True
                dfs(i + 1)
                vis[j] = False

        n = len(nums)
        nums.sort()
        ans = []
        t = [0] * n
        vis = [False] * n
        dfs(0)
        return ans

要点:t = [0] * n 预分配定长列表,按位置写入;t[:] 在记录答案时拷贝快照,避免后续回溯改写污染已保存的结果。

4.2 Java

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int[] nums;
    private boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        vis = new boolean[nums.length];
        dfs(0);
        return ans;
    }

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

要点:Java 版本用成员变量承载 ans、t、nums、vis,路径用 t.add / t.remove(t.size() - 1) 动态维护;j > 0 与 Python 的 j 等价,用于避免数组越界。

4.3 C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> t(n);
        vector<bool> vis(n);
        auto dfs = & {
            if (i == n) {
                ans.emplace_back(t);
                return;
            }
            for (int j = 0; j < n; ++j) {
                if (vis[j] || (j && nums[j] == nums[j - 1] && !vis[j - 1])) {
                    continue;
                }
                t[i] = nums[j];
                vis[j] = true;
                dfs(i + 1);
                vis[j] = false;
            }
        };
        dfs(0);
        return ans;
    }
};

要点:该实现依赖 C++20 的 ranges::sort,并使用了带显式自身参数(this auto&& dfs)的递归 lambda,从而可以在函数体内直接递归调用自身。

4.4 Go

func permuteUnique(nums []int) (ans [][]int) {
	slices.Sort(nums)
	n := len(nums)
	t := make([]int, n)
	vis := make([]bool, n)
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			ans = append(ans, slices.Clone(t))
			return
		}
		for j := 0; j < n; j++ {
			if vis[j] || (j > 0 && nums[j] == nums[j-1] && !vis[j-1]) {
				continue
			}
			vis[j] = true
			t[i] = nums[j]
			dfs(i + 1)
			vis[j] = false
		}
	}
	dfs(0)
	return
}

要点:使用 slices.Sort(Go 1.21+)与 slices.Clone 拷贝快照;返回值通过命名返回值 (ans [][]int) 直接返回。

4.5 TypeScript

function permuteUnique(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans: number[][] = [];
    const t: number[] = Array(n);
    const vis: boolean[] = Array(n).fill(false);
    const dfs = (i: number) => {
        if (i === n) {
            ans.push(t.slice());
            return;
        }
        for (let j = 0; j < n; ++j) {
            if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            t[i] = nums[j];
            vis[j] = true;
            dfs(i + 1);
            vis[j] = false;
        }
    };
    dfs(0);
    return ans;
}

要点:由于 nums 可能包含负数,排序时显式传入比较函数 (a, b) => a - b,保证按数值升序而非字典序排列;t.slice() 生成快照副本。

4.6 Rust

impl Solution {
    pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let n = nums.len();
        let mut ans = Vec::new();
        let mut t = vec![0; n];
        let mut vis = vec![false; n];

        fn dfs(
            nums: &Vec<i32>,
            t: &mut Vec<i32>,
            vis: &mut Vec<bool>,
            ans: &mut Vec<Vec<i32>>,
            i: usize,
        ) {
            if i == nums.len() {
                ans.push(t.clone());
                return;
            }
            for j in 0..nums.len() {
                if vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1]) {
                    continue;
                }
                t[i] = nums[j];
                vis[j] = true;
                dfs(nums, t, vis, ans, i + 1);
                vis[j] = false;
            }
        }

        dfs(&nums, &mut t, &mut vis, &mut ans, 0);
        ans
    }
}

要点:Rust 的递归函数不能直接闭包捕获多个可变借用,因此将 nums、t、vis、ans 全部作为参数显式传入,通过 &mut 共享可变状态;t.clone() 产生排列快照。

4.7 JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans = [];
    const t = Array(n);
    const vis = Array(n).fill(false);
    const dfs = i => {
        if (i === n) {
            ans.push(t.slice());
            return;
        }
        for (let j = 0; j < n; ++j) {
            if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            t[i] = nums[j];
            vis[j] = true;
            dfs(i + 1);
            vis[j] = false;
        }
    };
    dfs(0);
    return ans;
};

要点:与 TypeScript 实现同构,t.slice() 在记录答案时复制当前排列,避免引用共享导致结果互相覆盖。

4.8 C#

public class Solution {
    private List<IList<int>> ans = new List<IList<int>>();
    private List<int> t = new List<int>();
    private int[] nums;
    private bool[] vis;

    public IList<IList<int>> PermuteUnique(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        vis = new bool[n];
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.Length) {
            ans.Add(new List<int>(t));
            return;
        }
        for (int j = 0; j < nums.Length; ++j) {
            if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            vis[j] = true;
            t.Add(nums[j]);
            dfs(i + 1);
            t.RemoveAt(t.Count - 1);
            vis[j] = false;
        }
    }
}

要点:与 Java 版结构一致,通过 new List<int>(t) 拷贝快照、t.RemoveAt(t.Count - 1) 在回溯时撤销上一步选择。

五、复杂度分析

设数组长度为 n:

  • 时间复杂度:O(n × n!)。需要进行 n! 次枚举(去重后排列总数不超过 n!),每次枚举需要 O(n) 的时间来判断是否重复(主要开销在 vis 数组的扫描与相等性判断);
  • 空间复杂度:O(n)。递归深度为 n,需要一个长度 n 的标记数组 vis 记录每个位置是否被使用,以及长度 n 的排列构造数组 t;输出答案所占的空间不计入辅助空间。

结合题目约束 n <= 8,n! 最大为 8! = 40320,规模完全在可枚举范围内,该做法在实际运行中非常高效;同时 nums[i] 取值范围为 [-10, 10],排序与相等性判断均不涉及溢出等边界问题。

六、仓库源码与相似题目

  • 本题完整文档与全部实现:README.md(中文)、README_EN.md(英文);
  • 各语言独立源码文件:Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs,均位于 solution/0000-0099/0047.Permutations II/ 目录下,可直接对照阅读或本地运行验证;
  • 相似题目:46. 全排列——无重复元素的回溯版本,是本题的前置基础。对比两道题的实现可以发现:47 题只是在 46 题的 if not vis[j] 基础上增加了一条去重剪枝条件,其余框架完全一致。掌握"先排序、再按值去重"的模式后,可以顺带推广到其他"含重复元素求组合/子集"类问题(如仓库中 剑指 Offer II 083/084 的全排列系列题解),去重思路一脉相承。
登录后查看全文
leetcode