题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
思考
- 1、和上一题全排列1基本一直一致
- 2、然后我们还需要横向去重（相同的我们就不用了，很简单的道理，我前面排列的值，一定包含后面值）
- 3、所以我们要先排序
代码和注释
/**
全排列=》回溯
*/
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
// 0未使用，1已使用
int[] used = new int[nums.length];
Arrays.sort(nums);
backtacking(nums,used);
return res;
}
public void backtacking(int[] nums, int[] used){
// 终止条件
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] == 0){
continue;
}
// 对于排列中同一个树枝是不是用过，因为在排列中，我们还是要用前面的元素，那么当前元素也有，so需要判断
if(used[i] == 0){
// 标记为使用过
used[i] = 1;
path.add(nums[i]);
backtacking(nums,used);
path.removeLast();
used[i] = 0;
}
}
}
}
总结
- 1、横向去重方案，使用一个used数值，并判断前面的值是不是相等
- 2、判断一个树枝上的值是否已经使用过，试用于全排列相关的题目
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96124.html
