LeetCode 39: 组合总数
题目描述
解题思路：回溯算法
1.回溯算法：
回溯算法其实实际上是一个类似枚举的搜索尝试过程，将可能出现的所有情况都进行一边搜索一边枚举，然后根据条件进行判断当前分支是否满足条件。如果正好满足条件则加入结果集，结束当前回溯分支；如果不满足条件则根据情况判断是继续深入当前分支还是结束当前分支返回上一层。多说无益，接下来用图来展示这道题的解题思路。
我们采用candicate = [2,3,5], target = 8;分析这道题目
先贴上代码
本体代码的核心在于dfs函数，dfs函数是用来进行回溯的核心函数，其中三个参数分别是 sum：当前分支的所有数字的和；conbine：当前分支的组合方式；index：当前分支的开始遍历的数组下标。
回溯算法其中很重要的一部分在于把握当前分支的是否满足条件，即把握住出口。本题的出口有两个：（1）当前回溯分支的sum > target，证明不满足条件，跳出当前分支搜索另一种可能；（2）当前回溯分支的sum === target，表明找到了一种解，存入解集中，再结束当前分支，继续搜索。
接下来就是本题的核心，如果遍历所有的分支，找到所有存在的解。下图是本题的分支树
对于candidate中的三个数，进行循环遍历，所以在树的第一层分别是2，3，5；我们从头开始用2来进行模拟。
此时index = 0；combine = [2]; 然后递归调用dfs函数。在递归调用的dfs函数中，三个入参分别是sum = 2，combine = [2]，index = 0；此时进行条件判断，sum > target 和sum === target均不满足，进行第二层的搜索。此时 第二次调用dfs函数的参数分别为sum = 4，combine = [2，2]，index = 0；再重复上述步骤进行条件判断，发现依然不满足。进行第三次调用 三个参数为 sum = 6, combine = [2,2,2], index = 0;还是不满足条件，进行第四次调用，此时 sum = 8, combine = [2,2,2,2],index = 0; 到这个时候我们可以看到sum为8，满足sum === target条件。那么此时就应该将这个解保存进入解集中。
接下来就可能是比较难理解的一部分，当我跳出这个分支然后呢？其实可以这么想，想想你在走迷宫，走着走着你发现走进了一条死路，这个时候该怎么办呢？我们是不是应该回头找另一条路呢？回溯算法也是如此，在我们发现当前分支已经没办法继续走下去的时候就退出分支。在代码中是这么体现的
使用Array.pop()方法将当前分支组合中的最后一个参数退出，还是使用 sum = 8, combine = [2,2,2,2],index = 0;来进行模拟，当前运行环境下因为已经满足条件，就会执行return语句，跳出当前执行上下文，进入到上一层的执行上下文中的下一个语句，即sum = 6，combine = [2,2,2],index = 0;这一层中 combine.pop()语句。即下图中红圈的这一个执行环境中。
接下来就执行for循环中i++语句，那么此时的情况是不是变成了sum = 6, combine = [2,2,2]和i = 1了？。接下来继续红圈中的语句，combine.push(candidate[i])；就把candidate[1]加了进去，再执行dfs函数 sum = 9，combine = [2,2,2,3]， i = 1。在后续的操作就如出一辙了，不再赘述。直到走到最后为[5,5]的情况，该搜索也就到了头，回溯算法结束，此时res中已经加入了所有的可能的解，本题结束。
递归回溯的算法一开始接触可能比较难以理解的就职其中递归的步骤，其实只要把自己代入进运行环境中，一步步的执行，弄清楚的话就会慢慢的发现，其实递归就是那点事儿。
类似的题目在力扣中还有很多，本题属于相当基础的回溯题目，没有考虑到去重的情况。比如力扣的第40题，相关的题解写在另一篇文章中，欢迎参阅。
