39. 组合总和

image.png

解题思路

典型的回溯法：
递归跳出的条件
return

满足题目条件
将list加入容器
else 未满足条件：
for（遍历给出的所有变量）{
（为了去重，往往加start，来控制递归，遍历之后的元素）
将元素加入到list
递归这个函数
去除当前list的最后一个元素
}

回溯原理类似树，不断的选择，剪枝，直到把所有结果都遍历到

image.png

代码

class Solution {
     List<List<Integer>> res=new ArrayList<>();
     public List<List<Integer>> combinationSum(int[] candidates, int target) {
         if (candidates == null || candidates.length == 0 || target < 0) {
            return res;
        }

        int start=0;
         List<Integer> list=new ArrayList<>();
         digui(start,target,candidates,list);

         return res;
     }
     public void digui(int start,int target,int [] candidates,List<Integer> list){
         if(target<0) 
             return;
          if(target==0){
             res.add(new ArrayList<>(list));
          }else {
              for(int i=start;i<candidates.length;i++){//不用去重
                  list.add(candidates[i]);
                  digui(i,target-candidates[i],candidates,list);
                  list.remove(list.size()-1);//溯回,去数组的最后一个元素
              }
          }
     }
}