代码随想录补|leetcode 46、47全排列问题

46.力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这道题和组合问题不同的是，本题允许[1,2,3][1,3,2]这种重复的，所以就不需要for循环时设定开始的索引避免重复。只需要先判断一下list集合里是不是有过这个元素了？如果有了，就continue本轮。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtracking(nums);
        return result;
    }
    public void backtracking(int[] nums){
        if(list.size() == nums.length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0 ; i < nums.length; i++){
            if(list.contains(nums[i])){
                continue;
            }
            list.add(nums[i]);
            backtracking(nums);
            list.remove(list.size() - 1);
        }
    }
}

47.https://leetcode.cn/problems/permutations-ii/description/

这道题和上面不同的地方是本题的nums数组允许有重复，涉及去重问题。我们前面讲到了去重有两种方法：
1.nums数组可以进行sort——used数组去重

2.nums数组里的数不能随意改变顺序——set集合去重

本题显然是可以sort改变内部数的顺序的，所以本题采用used数组去重：

解释和day24-CSDN博客的40题一样，i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0时，continue；此外，和46一样，当list.contains(nums[i]) && used[i] == 1时，说明竖着的已经用过这个数了，也需要continue

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        backtracking(nums,used);
        return result;
    }
    public void backtracking(int[] nums, int[] used){
        if(nums.length == list.size()){
            result.add(new ArrayList<>(list));
            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;
            }
            list.add(nums[i]);
            used[i] = 1;
            backtracking(nums,used);
            used[i] = 0;
            list.remove(list.size() - 1);
        }
    }
}