思路:排列问题和组合问题最大的不同在于,排列是有序的[1,2,3]和[2,1,3]是不同的,这就意味这第一个排序中出现的数值在第二个排序中还会出现,所以我们在进行for循环的时候,不再需要start来控制每次的起点,因为每次都直接从0开始,从头到尾完整的走一遍。本题提供的排列数组是不含重复数字的,所以我们只需要用used数组来控制每个排序中的数字只出现一次即可,即不会出现[1,1,2]这样的情况。
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> list = new LinkedList<>();
boolean[] uesd;
public List<List<Integer>> permute(int[] nums) {
// 使用used数组判断一个排列中是否重复
uesd = new boolean[nums.length];
backTracking(nums,uesd);
return res;
}
public void backTracking(int[] nums,boolean[] uesd){
if (list.size() == nums.length){
res.add(new ArrayList<>(list));
}
//排列问题是有序的[1,2]和[2,1]是不同的 所以i 不用从start开始
// 而且每次都需要从头开始搜起
for (int i = 0; i < nums.length;i++){
// 单个排列中一个数字只能出现一次
if (uesd[i] == true) continue;
uesd[i] = true;
list.add(nums[i]);
backTracking(nums,uesd);
//回溯
list.remove(list.size() -1 );
uesd[i] = false;
}
}
}
思路:和上一题不同,本题提供的数组中包含了重复的数字,例如[1,1,2] 那么虽然有两个1 但是排列[1,1,2]只能有一个 所以本题需要去重,我们依然使用排序加uesd数组的方式 排除同一个树层中出现过的数字。
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> list = new LinkedList<>();
boolean[] uesd;
public List<List<Integer>> permuteUnique(int[] nums) {
// 使用排序加上used数组
Arrays.sort(nums);
uesd = new boolean[nums.length];
// Arrays.fill(uesd,false);
backTracking(nums,uesd);
return res;
}
public void backTracking(int[] nums,boolean[] uesd){
if (list.size() == nums.length){
res.add(new ArrayList<>(list));
return;
}
//排列问题是有序的[1,2]和[2,1]是不同的 所以i 不用从start开始
// 而且每次都需要从头开始搜起
for (int i = 0; i < nums.length;i++){
// 单个排列中一个数字只能出现一次
if (uesd[i] == true) continue;
// 去重 当个树层中一个数字只能出现一次
// 当i = 0时 i-1为负数会报错
if (i > 0 && nums[i] == nums[i - 1] && uesd[i -1 ] == false) continue;
// 当同一树枝的值未使用过
// if (uesd[i] == false) {
uesd[i] = true;
list.add(nums[i]);
backTracking(nums, uesd);
//回溯
list.remove(list.size() - 1);
uesd[i] = false;
// }
}
}
}