LeetCode第39题组合总和

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

分析一波题目

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

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

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

下面是示意图，我们每次都从子节点上取一个数据作为组合的元素，不断的取，直到满足组合条件为止，取到一个之后我们需要回退回来，继续找。

解题关键

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

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

编码解决

class Solution {

    private List result = new ArrayList();

    public List combinationSum(int[] candidates, int target) {
        //递归 回溯

        backtracking(candidates,target, new ArrayList(), 0, 0);

        return result;
    }
    public void backtracking(int[] candidates, int target,List path, int startIndex, int sum) {
        //结束条件

        if(sum == target) {

            result.add(new ArrayList(path));

            return;

        }

        if(sum > target) {

            return;

        }

        //递归单层逻辑

        for(int i=startIndex; i