47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

首先排序,对于有重复数据的数组,排序可以方便剪枝。
回溯,每次遍历数组内的元素。
创建一个数组记录元素是否已被遍历。
遍历时如果数组已经被记录,或者当前元素与数组中的上一个元素相等,且上一个数组未被选择,则跳过。
(如果上一个同样的数字没被选择,则放弃这个排列。即在元素相同时,优先选择前面的元素进行排列)

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
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
Arrays.sort(nums);
int[] visited = new int[nums.length];
backtracking(ret, new ArrayList<>(), visited , nums);

return ret;
}

private void backtracking(List<List<Integer>> ret, List<Integer> arr, int[] visited, int[] nums){
if(arr.size() == nums.length){
ret.add(new LinkedList<>(arr));
return;
}

for(int i = 0; i < nums.length; i++){
if(visited[i] == 1) continue;
if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue;
arr.add(nums[i]);
visited[i] = 1;
backtracking(ret, arr, visited, nums);
visited[i] = 0;
arr.remove(arr.size()-1);
}
}
}
Author

Xander

Posted on

2022-04-25

Updated on

2022-04-24

Licensed under

Comments