力扣第39题：组合总和（java回溯）

本文主要是介绍力扣第39题：组合总和（java回溯），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 一、题目内容

二、题目分析

        这道题目的示例[2,3,6,7]，可以用下图方式遍历的理解。

        如图，首先有四种选择方法，可以在2,3,6,7中任选一个，然后将它加到临时列表中去，之后每层都有四种选择方法（因为可重复选择），每次选择后我们用sum+=选择的值，当我们一直选择到sum等于target的时候，说明我们找到了一种情况满足条件，那我们就将这一临时列表加到结果列表里去，如果sum>target,则说明当前的值不应该选择，直接return即可。只有当sum<target时，才可以进行下去，遍历整数数组，然后加入当前数值，回溯，撤销。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list =new ArrayList<> ();
        Arrays.sort(candidates);
        backtrack(list,new ArrayList<>(),candidates,target,0);
        return list;
    }
    public void backtrack(List<List<Integer>> list,List<Integer> templist,int []candidates,int target,int index)
    {
        if(sum(templist)==target)
        {
            list.add(new ArrayList<>(templist));
            return;
        }
        if(sum(templist)>target)
            return;
        for(int i=index;i<candidates.length;i++)
        {
            templist.add(candidates[i]);
            backtrack(list,templist,candidates,target,i);
            templist.remove(templist.size()-1);
        }
    }
    public int sum(List<Integer> l)
    {
        int s=0;
        for(int i=0;i<l.size();i++)
        {
            s+=l.get(i);
        }
        return s;
    }
}

这篇关于力扣第39题：组合总和（java回溯）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！