算法题补充

前言

我需要补充一些烧鸡100和剑指offer没有的题目

回溯

47. 全排列 II - 力扣（LeetCode）

主要是掌握去重的套路

1. 排序

2. visit[]

3. if(i>0&&nums[i]==nums[i-1]&&!visit[i-1])

   class Solution {
       List<Integer>path=new ArrayList<>();
       ArrayList<List<Integer>>res=new ArrayList<>();//设为全局变量就不用传递参数了
       public List<List<Integer>> permuteUnique(int[] nums) {
           Arrays.sort(nums);
           boolean[]used=new boolean[nums.length];
           back(nums,used);
           return res;
       }
   
       public void back(int[]nums,boolean[]used)
       {
           if(path.size()==nums.length)
           {
               res.add(new ArrayList<>(path));
               return;
           }
           for(int i=0;i<nums.length;i++)
           {
               if(used[i]==true)
               {
                   continue;
               }
               if(i>0&&nums[i]==nums[i-1]&&!used[i-1])
               {
                   continue;
               }
               path.add(nums[i]);
               used[i]=true;
               back(nums,used);
               path.remove(path.size()-1);
               used[i]=false;
           }
       }
   }

具体为什么，建议看傻逼卡尔的讲解