原题说明：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
注意：有数字（包括 target）都是正整数。解集不能包含重复的组合。
原题链接：https://leetcode-cn.com/problems/combination-sum
题目分析：
这道题目一拿到手，想到的就是两个递归和动态规划。委实说，到写这篇博客之时，我对这些算法还是分不太清楚。希望每周一次的算法/数据结构学习能改善这样的局面。
这道题目我是查看了题解和一些人给的代码。尽管如此，我还是能以自己的理解来表达这个问题。
官方的题解和大多数人的评论都是回溯算法，那么关于这个算法，截止写这篇博客时我不甚了解，这里主要是给出怎么运用这样的算法。我有看到一些人说，回溯算法是一种思想，可能实现方式是依靠递归？
下面进入正题，这次的博客将按照从无到有的顺序介绍代码。
首先，这里先引一段网友给出的思路：
1. 定义全局结果数组
2. 返回全局结果数组
3. 调用递归函数
4. 定义递归函数1) 参数，动态变化，一般为分支结果、限制条件等
2) 终止条件，将分支结果添加到全局数组
3) 调用递归逐步产生结果，回溯搜索下一结果
4) 剪枝条件
我按照自己的理解、并参考了大家的代码，完成了解题。
第一&二步，定义全局结果数组
public ArrayList<ArrayList<Integer>> easyversion(int[] candidates, int target) {
ArrayList<ArrayList<Integer>> res1 = new ArrayList<ArrayList<Integer>>();
return res1;
}
这里$res1$就是结果数组，当然数据结构不一定是List形式。我有看到一些题解将这个参数作为全局变量，这样就可以避免在每次调用递归函数的时候，多传入一个固定的变量了。
第三步，调用递归函数
public ArrayList<ArrayList<Integer>> easyversion(int[] candidates, int target) {
ArrayList<ArrayList<Integer>> res1 = new ArrayList<ArrayList<Integer>>();
backtracking_easy(candidates, 0, target, res1, new ArrayList<Integer>());
return res1;
}
第三行就是递归函数。这里我回想起之前听过的课程，其实对于函数接口的设计有两种方案：其一就是事先想好，都需要实现哪些方法，然后在设计的时候就完成编写；其二就是将一些反复出现的操作封装起来，设计好输入和输出的形式，之后再编写方法。
其实对于第三行代码， new ArrayList<Integer>()在这里其实是没有意义的，但是考虑到递归函数调用的统一，需要有这个参数传递。
第四步，定义递归函数
图1展示的是本题的回溯过程（以$[1,2,3,4,5,6]$为给定数组，$target=6$）
STEP1. 参数动态变化（分支结构和限制条件）
private void backtracking_easy(int[] nums, int start, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
if(target<0) {
}
else if(target==0) {
}
else {
}
}
这里先说明递归函数传入的各个参数的含义。$nums$是提供的数组，$start$是当前遍历的起点，$target$是当前的目标值，$res1$是全局结果的返回值，$list$是当前存储组合的参数。
从图1中可以看到，回溯的思路，就是穷尽组合时，不断计算组合的加和。这个时候$target$不断变化，直到满足条件（$target==0$）。因此这也就是递归的分支和限制条件。
分别就三种条件讨论：
$target<0$。说明上一层加入的新元素使得组合总数超过了目标值，因此要返回上一层并剪枝（移除新加入的元素），之后在考虑加入下一个元素；
$target==0$。说明正好满足条件，加入新元素之后的$list$可以append到$res1$中。再返回上一层，同样也要剪枝并考虑加入下一元素；
$target>0$。说明达到目标值仍然需要加入元素。$start$代表的索引就是刚加入的元素位置，应当以此为起点，继续加入该元素。
STEP2. 终止条件设定
private void backtracking_easy(int[] nums, int start, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
if(target<0) {
return;
}
else if(target==0) {
res.add(new ArrayList<>(list));
return;
}
else {
for(int i = start; i < nums.length; i++) {
}
}
}
因为要求是找到所有组合，所以这里就是循环遍历。循环变量$i$的初始条件在$target>$已经提到了。这里的终止条件本来有两个（参考其它的答案），其一是元素的遍历不能发生数组越界$i<nums.length$，其二是组合的加和不超过目标值$target>0$。逐个分析一下：
第一点是为了保证数组的元素能都被遍历，穷尽所有的组合可能；
第二点是为了能够加入新的元素，逐渐接近目标值。但是因为之前有分支结果讨论过了，所以这点在这里就不必出现。
STEP3. 调用递归函数
private void backtracking_easy(int[] nums, int start, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
if(target<0) {
return;
}
else if(target==0) {
res.add(new ArrayList<>(list));
return;
}
else {
for(int i = start; i < nums.length; i++) {
//target -= nums[i]
list.add(nums[i]);
backtracking_easy(nums, i, target - nums[i], res, list);
}
}
}
在调用下一层递归函数之前，需要在当前存储的参数$list$中append新的加入的元素。若之后加和满足目标值，则可以将加入新元素之后的list再append到$res1$中；或再往其中加入新的元素、再返回（剪枝）；或返回（剪枝）。
之后就可以调用递归函数，进行递归（其实我认为这个函数不是递归函数，而是因为发生“自己调用自己”所以递归了）。
这里要注意的是，如果目标值先减去新加入的元素、再作为输入的参数加入到递归函数中，会产生错误的结果。
所以要将新的目标值放在递归的函数中，作为参数进行传递。
STEP4. 剪枝
private void backtracking_easy(int[] nums, int start, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
if(target<0) {
return;
}
else if(target==0) {
res.add(new ArrayList<>(list));
return;
}
else {
for(int i = start; i < nums.length; i++) {
list.add(nums[i]);
backtracking_easy(nums, i, target - nums[i], res, list);
list.remove(list.size()-1);//remove the last element
}
}
}
每次调用下层递归函数返回之后，只能有两种情况：$target<0$和$target==0$不管哪种情况，都说明当前加入的元素不满足组合加和的要求。因此需要从$list$中弹出当前元素，加入下个元素，直到遍历完数组中所有的元素。
以下是全部的代码
1 public ArrayList<ArrayList<Integer>> easyversion(int[] candidates, int target) { 2 ArrayList<ArrayList<Integer>> res1 = new ArrayList<ArrayList<Integer>>(); 3 4 if(candidates == null && candidates.length < 1) 5 return res1; 6 7 Arrays.sort(candidates); 8 backtracking_easy(candidates, 0, target, res1, new ArrayList<Integer>()); 9 return res1; 10 } 11 12 private void backtracking_easy(int[] nums, int start, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) { 13 if(target<0) { 14 return; 15 } 16 else if(target==0) { 17 res.add(new ArrayList<>(list)); 18 return; 19 } 20 else { 21 for(int i = start; i < nums.length; i++) { 22 list.add(nums[i]); 23 backtracking_easy(nums, i, target - nums[i], res, list); 24 list.remove(list.size()-1);//remove the last element 25 } 26 } 27 }
在主函数部分，多出的代码首先是确保边界条件，还有就是对给定的数组进行排序，提高效率。对于数组中重复的元素，其实可以看做是再加入一个已有的元素，所以并不会有影响。
下面是一个简单的递归实例说明，给定的数组是$[2,1,3]$（故意没有排序的），目标值是3。
总结：
原文：https://www.cnblogs.com/RicardoIsLearning/p/12076579.html