文章

[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)

总结

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

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

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

License:  CC BY 4.0