题目描述
给定一个可包含重复数字的序列，返回所有不重复的全排列。
解题思路
1、题意理解，该序列有重复的数字，需要用一个boolean变量来标记该数字是否已经加入列表中 2、如果无法想象需要在哪里剪枝，画图。这里以[1,1,2]的全排列为例。圈蓝圈的表示需要剪枝的地方。代码：i > 0 && nums[i] == nums[i -1] && !used[i - 1]表示剪枝的地方
1、题意理解，该序列有重复的数字，需要用一个boolean变量来标记该数字是否已经加入列表中
代码
class Solution {
public List
<List
<Integer>> permuteUnique(int[] nums
) {
List
<List
<Integer>> list
= new ArrayList<>();
Arrays
.sort(nums
);
backtrack(list
, new ArrayList<>(), nums
, new boolean[nums
.length
]);
return list
;
}
private void backtrack(List
<List
<Integer>> list
, List
<Integer> tempList
, int[] nums
, boolean[] used
){
if(tempList
.size() == nums
.length
){
list
.add(new ArrayList<>(tempList
));
}else{
for(int i
= 0; i
<nums
.length
; i
++){
if(used
[i
] || i
> 0 && nums
[i
] == nums
[i
-1] && !used
[i
- 1]) continue;
used
[i
] = true;
tempList
.add(nums
[i
]);
backtrack(list
, tempList
, nums
, used
);
used
[i
] = false;
tempList
.remove(tempList
.size() - 1);
}
}
}
}
参考：https://leetcode.com/problems/permutations-ii/discuss/18648/Share-my-Java-code-with-detailed-explanantion
