LeetCode第39题组合总和

继续打卡算法题，今天学习的是LeetCode的第39题组合总和，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

组合问题如果通过枚举发现还是很难的，因为他涉及到嵌套多层for循环的情况，这个时我们需要使用回溯法。

回溯法是通过递归来实现的。通过递归代替多层嵌套循环。

我们可以把获取组合数据的过程，想成在遍历一棵树，每个节点上都有可以选择的数字。

下面是示意图，我们每次都从子节点上取一个数据作为组合的元素，不断的取，直到满足组合条件为止，取到一个之后我们需要回退回来，继续找，题目说明每个数字可以重复使用，也就是每次都需要考虑先取自己作为组合的元素。

解题关键

1、递归法解决嵌套循环问题

2、递归结束条件控制，找到了组合的数据就结束，或者组合已经大于target了，也要结束递归。

编码解决

class Solution {

    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        //递归 回溯
        backtracking(candidates,target, new ArrayList<>(), 0, 0);
        return result;

    }

    public void backtracking(int[] candidates, int target,List<Integer> path, int startIndex, int sum) {

        //结束条件
        if(sum == target) {
            result.add(new ArrayList(path));
            return;
        }
        if(sum > target) {
            return;
        }
        //递归单层逻辑
        for(int i=startIndex; i<candidates.length; i++) {
               
               path.add(candidates[i]);
               sum += candidates[i];
               //开始递归 startIndex传i,就是考虑每个数字都可以重复使用的情况
               backtracking(candidates, target, path, i, sum);
               //回溯
               sum = sum - candidates[i];
               path.remove(path.size()-1);
        }
    }
}

总结

回溯法通过递归解决多层嵌套循环的问题，以后记得多层嵌套循环的情况就可以考虑使用递归是否合适。