回溯算法

回溯算法其实就是把所有的结果进行枚举，通过设定条件函数来搜索目标解
做搜索、回溯问题的套路是画图，代码其实就是根据画出的树形图写出来的
剪枝函数：描述合法解的一般特征，避免搜索不合法解
条件：每一步搜索的解必须符合条件，其所有可能的解可以由空间状态树进行描述
记录：当每次达到结束条件时对结果进行保存，通常是全局变量并作为传递参数
这里以力扣39：组合总和，liweiwei1419 的解答过程进行描述：
要求找数组中元素和满足目标值的元素排列，元素可以重复；它这里采用减的方式，将解空间进行表述。
示例：输入: candidates = [2, 3, 6, 7]，target = 7，所求解集为: [[7], [2, 2, 3]]
这里，只有最后的条件满足为0的数组元素记录返回就行，通过递归调用的方式，当然我这用了累减和累加的两种形式，

class Solution {
    //采用数组元素累加和和满足目标值的解答过程，
    /*List <List<Integer>>  list = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List <Integer> ls = new ArrayList<>();
        int[] arr =candidates;
        search(arr,0,ls,0,target); //目标数组，当前索引，子列表集合，当前和，目标和
        return list;
    }
     public void search(int[] arr,int index,List <Integer> ls,int sum,int target){
      if(sum> target){
          return;
      }else if(sum==target){
         List<Integer> e = new ArrayList<Integer>();
         e.addAll(ls); //记录所有满足条件的，
        list.add(e); 
        return;
      }
      for(int i=index;i<arr.length;i++){
         if(arr[i]>target){continue;}  //跳过不符合的值
         ls.add(arr[i]);
         search(arr,i,ls,sum+arr[i],target); //执行完后返回  
         ls.remove(ls.size()-1);//根据下标去掉最后一个元素，最后一个(当前元素不满足时跳过)
      }

     }*/

     //利用减法来做，只有当最后的值为0时作为回溯条件
     List <List<Integer>>  list = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List <Integer> ls = new ArrayList<>();   //每次获得子集合的目标元素会进行再次清空处理
        int[] arr =candidates;
        search(arr,0,ls,target,target); //目标数组，当前索引，子列表集合，当前减值，目标和
        return list;
    }
     public void search(int[] arr,int index,List <Integer> ls,int delete,int target){
      if(delete < 0){
          return;
      }else if(delete==0){
         List<Integer> e = new ArrayList<Integer>();
         e.addAll(ls); //记录所有满足条件的，
        list.add(e); 
        return;
      }
      for(int i=index;i<arr.length;i++){
         if(arr[i]>target){continue;}  //跳过不符合的值
         ls.add(arr[i]);
         search(arr,i,ls,delete-arr[i],target); 
         //执行完后返回，索引还是当前的索引，可能满足同一个元素的倍数情形  
         ls.remove(ls.size()-1);//根据下标去掉最后一个元素，当最后一个(当前元素不满足时跳过)
      }

     }
}

力扣40题：组合总和II，这里要求元素不能重复使用，且不能有相同的排列出现。

与39不同的是，这里每次返回的索引一定是指向下一个，使得每个元素不被重复使用，
这里没有TreeSet排序，利用数组排序来避免出现重复的排列，
当然也可以一开始就进行排序，后面的结果肯定没有重复：这里采用和的形式判断

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> lst = new ArrayList<>();
        int[] arr = candidates;
        search(arr,0,lst,0,target);//目标数组，当前索引，子列表集合，当前和，目标和
        return list;
    }
    public void search(int[] arr,int index,List<Integer> lst,int sum,int target){
      if(sum>target){
          return;
      }
      if(sum == target){
         List<Integer> temp = new ArrayList<>();
         //HashSet<Integer> hs = new HashSet<>();
         //集合转数组，数组转集合
         Integer[] brr = new Integer[lst.size()];
         lst.toArray(brr);
         Arrays.sort(brr);
         temp = Arrays.asList(brr);
         
         if(list.contains(temp)){ //判断大集合是否有重复，重复跳过
             return;
         }
         list.add(temp);
         return;
         
      }
      for(int i=index;i<arr.length;i++){
          if(arr[i]>target){continue;}
          //if(lst.contains(arr[i])){ continue;}//判断是否元素重复
        lst.add(arr[i]);
        search(arr,i+1,lst,sum+arr[i],target); //避免原来用过的元素重复使用
        lst.remove(lst.size()-1);//根据下标去掉最后一个元素，最后一个(当前元素不满足时跳过)
          
      }
    }
}