[LeetCode] 每日一题 47. 全排列 II

题目链接

https://leetcode.cn/problems/permutations-ii

题目描述

给定一个可包含重复数字的序列 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. 排序：首先对数组进行排序，确保相同的元素相邻，从而方便去重

2. 回溯：通过回溯算法生成排列，每次递归时，尝试将当前元素添加到路径中，直到路径的长度达到 nums.length

3. 去重条件：如果当前元素和前一个元素相同，并且前一个元素没有被使用过，或者当前元素已经被使用过，应该跳过该元素，避免生成重复的排列

代码实现

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    private void backtrack(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] || used[i]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

复杂度分析

• 时间复杂度：O(n! * n)，其中 n 是数组的长度。最坏情况下，所有的全排列数量为 n!，对于每一个排列，我们需要花费 O(n) 的时间来构建该排列

• 空间复杂度：O(n)，用于存储路径和递归栈的空间。递归的深度最大为 n，同时路径的长度也是 n，因此空间复杂度为 O(n)

总结

本题采用回溯算法来生成所有可能的排列，并结合排序和去重策略有效避免了重复的排列。通过每次递归选择当前元素并更新路径，我们能够探索所有排列，同时通过判断条件避免了重复的排列被添加到结果中。

回溯算法非常适合这种枚举所有可能的解法问题，且去重操作确保了生成的解集是唯一的。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。