[LeetCode] 每日一题 47. 全排列 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
解题思路
本题要求返回给定序列的所有不重复的全排列。由于序列中可能包含重复的数字,我们需要采用回溯算法,并结合去重的策略来避免生成重复的排列
回溯算法:
排序:首先对数组进行排序,确保相同的元素相邻,从而方便去重
回溯:通过回溯算法生成排列,每次递归时,尝试将当前元素添加到路径中,直到路径的长度达到
nums.length
去重条件:如果当前元素和前一个元素相同,并且前一个元素没有被使用过,或者当前元素已经被使用过,应该跳过该元素,避免生成重复的排列
代码实现
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