day24逆增子序列&全排列&全排列II（全排列问题：回溯三部曲）

        今天学习回溯的全排列问题，分为两种：一种包含重复元素，一种不包含重复元素。

1.力扣491（逆增子序列）

        本题因为每个元素只能使用一次，所以我们需要下标来记录带开始的位置，其次本题特殊的地方在于保证递归子序列的递增性，所以我们在遍历时要进行判断是否满足递增，不满足的直接continue。回溯三部曲：

• 递归函数参数：本题求子序列，很明显一个元素不能重复使用，所以需要startIndex，调整下一层递归的起始位置。

    public void backtraveling(int[] nums,int startIndex)

• 终止条件：本题其实类似求子集问题，也是要遍历树形结构找每一个节点，可以不加终止条件，startIndex每次都会加1，且本题的特殊是最少两个元素才能加入队列。

        if(path.size()>1){
            res.add(new ArrayList(path));
        }

• 单层递归逻辑：跟求子集问题类似，只需要我们处理下不满足递增性的节点不加入即可

        int[] used = new int[201];
        for(int i=startIndex;i
            //树层去重
            if(!path.isEmpty()&&nums[i]1)||used[nums[i]+100]==1){
                continue;
            }
            path.add(nums[i]);
            used[nums[i]+100]=1;
            backtraveling(nums,i+1);
            path.remove(path.size()-1);
        }

整体代码：

    List> res = new ArrayList();
    List path = new ArrayList();
    public List> findSubsequences(int[] nums) {
        backtraveling(nums,0);
        return res;
    }
    public void backtraveling(int[] nums,int startIndex){
        if(path.size()>1){
            res.add(new ArrayList(path));
        }
        int[] used = new int[201];
        for(int i=startIndex;i
            //树层去重
            if(!path.isEmpty()&&nums[i]1)||used[nums[i]+100]==1){
                continue;
            }
            path.add(nums[i]);
            used[nums[i]+100]=1;
            backtraveling(nums,i+1);
            path.remove(path.size()-1);
        }
    }

2.力扣46（全排列）

        本题难点在于去重的操作，其他步骤和收集叶子节点的问题一样，只需要在尾节点处添加收集path即可，而我们怎么去重呢？也很简单，我们先定义一个used数组，我们在进行下次for循环时需要used【i】==true时，证明此元素使用过，就直接continue就可以达到去重了。回溯三部曲：

• 递归函数参数：首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，也就是从0开始，所以处理排列问题就不用使用startIndex了。

    public void backtravling(int[] nums) 

• 递归终止条件：当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

        if(path.size()==nums.length){   
            res.add(new ArrayList(path));
            return;
        }

• 单层搜索的逻辑：因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

        for(int i=0;i
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            backtravling(nums);
            used[i] = false;
            path.remove(path.size()-1);
        }

整体代码：

    List> res = new ArrayList();
    List path = new ArrayList();
    boolean[] used;
    public List> permute(int[] nums) {
        used = new boolean[nums.length];
        Arrays.fill(used,false);
        backtravling(nums);
        return res;
    }
    public void backtravling(int[] nums) {
        if(path.size()==nums.length){   
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            backtravling(nums);
            used[i] = false;
            path.remove(path.size()-1);
        }
    }

3.力扣47（全排列II）

         本题是对上一个全排列问题的升级版，因为给我们的数组是包含重复元素的，所以我们不仅需要使用used【i】==true时跳过，我们还需要使用 i>0&&nums[i]==nums[i-1]&&！used[i-1]条件，若满足就跳过，也就是说我们在树层遍历时，碰到相同元素时，前面的元素的used【i-1】==false时跳过。

整体代码：

    List> res = new ArrayList();
    List path = new ArrayList();
    boolean[] used;
    public List> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.fill(used,false);
        Arrays.sort(nums);
        backtraveling(nums);
        return res;
    }
    public void backtraveling(int[] nums) {
        if(path.size()==nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i=0;i
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            if(!used[i]){
            path.add(nums[i]);
            used[i] = true;
            backtraveling(nums);
            used[i] = false;
            path.remove(path.size()-1);
            }
        }
    }