【排列回溯】Leetcode 46. 全排列 47. 全排列 II
- 46 全排列——used数组上下层保证不取重复的即可
- 47. 全排列 II——used去重上下层,再去重本层重复元素
46 全排列——used数组上下层保证不取重复的即可
---------------🎈🎈题目链接🎈🎈-------------------
used数组,其实就是记录此时temp 里都有哪些元素使用了,这样就保证每一层都可以取剩下的,即一个排列里一个元素只能使用一次。
排列都是从0开始遍历for循环,跳过used中为1 的元素即可。
组合都是从startindex开始遍历for循环,保证不重复
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int[] used = new int[nums.length];
helper(nums,used);
return result;
}
public void helper(int[] nums, int[] used){
// 当temp的长度等于nums的长度的时候就可以收获一个结果啦
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[i] == 1){ // 如果当前的这个元素已经被前层使用过了,那么used中对应位置会置为1,本层就不使用了
continue;
}
temp.add(nums[i]);
used[i] = 1;
helper(nums,used);
temp.removeLast();
used[i] = 0;
}
}
}
47. 全排列 II——used去重上下层,再去重本层重复元素
---------------🎈🎈题目链接🎈🎈-------------------
这道题目和46.全排列 (opens new window)的区别在与:
给定一个可包含重复数字的序列,要返回所有不重复的全排列。
去重需要先排序!
对于前后层(可以选取相等的元素):使用used数组,如果前层使用了元素,used[i]就置为1。递归到下一层的时候如果used[i] == 1,那么就跳过
对于同一层(不选取相等的元素):当i > 0且 前后两个元素相等:nums[i] == nums[i-1],如果此时的used[i-1] = 0,代表当前元素nums[i] 的前一个元素目前未被使用,说明同层有重复的元素nums[i] 和nums[i-1],所以跳过!⭐️if(i>0 && nums[i] == nums[i-1] && used[i-1]==0|| used[i] == 1){ continue; }
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
int[] used = new int[nums.length];
Arrays.sort(nums);
helper(nums,used);
return result;
}
public void helper(int[] nums, int[] used){
//temp中长度和nums相同,那么就收货结果
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
//如果同层中遇到两个相等 且 当前的这个元素已经被前层使用过了 那么就跳过
if(i>0 && nums[i] == nums[i-1] && used[i-1]==0|| used[i] == 1){
continue;
}
temp.add(nums[i]);
used[i] = 1;
helper(nums,used);
used[i] = 0;
temp.removeLast();
}
}
}