image.png
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
Arrays.fill(used,false);
Arrays.sort(nums);
dfs(nums);
return result;
}
private void dfs(int[] nums) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if(i>0 && nums[i]==nums[i-1] && !used[i-1]){
continue;
}
//如果同⼀树⽀nums[i]没使⽤过开始处理
if(used[i]==false){
path.add(nums[i]);
used[i]=true;
dfs(nums);
used[i]=false;
path.remove(path.size()-1);
}
}
}
}
image.png
image.png
