美文网首页
39. 组合总和

39. 组合总和

作者: bangbang2 | 来源:发表于2020-07-11 14:34 被阅读0次
    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);//溯回,去数组的最后一个元素
                  }
              }
         }
    }
    

    相关文章

      网友评论

          本文标题:39. 组合总和

          本文链接:https://www.haomeiwen.com/subject/amkicktx.html