leetcode 47. 全排列 II
题目：47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
方法：Backtracking（回溯）
思路：Backtracking（回溯），用flag标记nums已中使用的元素，为避免重复排列，搜索前先对nums进行排序，每次搜索按顺序选取一个未被标记的元素加入排列集合，在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素（因为与之相等的前一个元素肯定在上一次排列中在这个位置出现过，回溯时是按顺序的），当排列集合满时，将排列集合加入结果集中，本次搜索结束，将元素标记、当前排列集合复原，进行下一次搜索。
运行数据：执行用时：1 ms，内存消耗：40.4 MB
复杂度分析：
- 时间复杂度：O(n * n!)，n为需要排列的元素个数，O(n!)为递归的时间复杂度，将结果加入结果集的时间复杂度为O(n)。
- 空间复杂度：O(n)，n为需要排列的元素个数，递归栈的深度为n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<List<Integer>>();
backtracking(nums, result, new ArrayList<>(), new boolean[nums.length]);
return result;
}
private void backtracking(int[] nums, List<List<Integer>> result, List<Integer> permuteUniqueList, boolean[] flag) {
if (nums.length == permuteUniqueList.size()) {
result.add(new ArrayList<>(permuteUniqueList));
return ;
}
for (int i = 0; i < nums.length; i++) {
if ((i != 0 && nums[i - 1] == nums[i] && !flag[i - 1]) || flag[i]) {
continue;
}
flag[i] = true;
permuteUniqueList.add(nums[i]);
backtracking(nums, result, permuteUniqueList, flag);
permuteUniqueList.remove(permuteUniqueList.size() - 1);
flag[i] = false;
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
