类似于限定排列组合问题，在此采用递归结构进行求解。
LeetCode原题如下：39. Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
?All numbers (including target) will be positive integers.
?The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题意：
给定一组非重复数字集合candidates，以及目标数字target。在candidates中选取一组数字组合（一个元素可多次出现），使这组数字累加求和结果为target。求所有组合结果。
分析：
看到这种列举组合问题，若是不求最优的情况下，多半考虑运用回溯算法；在此采用递归解决，简洁明了，虽然资源损耗较大（先挖几个坑）。
根据题意，在此先对给定元素集candidates进行自然排序（升序）以避免后续的重复组合运算判断（以更简单的方式保证单个组合在最终结果集中唯一），在元素集有序的情况下从index=0开始进行试探回溯。为在sum（candidates[…]）==target条件限定下得到候选组合，在此采用target逐减方式（也可采用total逐加方式进行判断），即在每得到一个候选数字的时候将target减去这个候选数得到新的target进行下一次候选元素判断，在此需要记录当前候选数字到候选组合result容器中，在result最终满足条件的情况下将其复制（深拷贝）一个副本保存到results中，至此得到一个满足条件的组合。
在候选元素选举的过程中，因为所有的候选集采用的都是同一个result容器，故而在这里需要在完成一次候选元素选取后进行一次末尾剪切（类似于前面一篇博客中的StringBuild运用问题：回溯算法复习（三） leetcode 22. Generate Parentheses 括号匹配拼接问题分析），也就是在result容器中删除最近加入的元素，而后进入下一次递归选举(回溯试探)；此外result容器的复用也呼应了前面所说的深拷贝问题。
在此对递归终止条件进行论述：
首先明确的是：当一个递归分支终止的时候也就意味着本次递归要么得到了一个满足条件的结果，要么由于当前候选元素不满足条件而退出递归（强行解释为回溯剪切）。列举如下：
1、index==candidates.length
索引越界，也就是没有候选元素可供选择。
2、candidates[index]>target
若将当前候选元素加入将导致sum（candidates[…]）大于给定初始target，即当前候选元素过大，不满足条件。
3、candidates[index]==target
当前元素加入后刚好满足条件，此时将result容器中的元素集复制一份加入results中。
除递归终止条件外还有一种情况便是candidates[index]<target此时意味着还有下一次候选元素加入的机会，此处就是递归执行体了。
在此对递归执行体进行一个简要论述：
可能需要提一下的是result.add(candidates[index]); combinationSum(candidates,index , target-candidates[index], result, results);这两行代码，为什么将当前index下标的元素加入候选集后还要让其进入下一次递归呢？这就涉及到代码复用的问题了。不妨假设没有这行代码，那么就需要在candidates[index]<target的情况下再写代码对当前候选元素进行一个判断吧，然后还要根据判断情况进行相应处理吧（当然也还有其它的代码优化方法，这只是其中一种），注意在当前调用运行时刻下上面的递归终止判断代码需要在index+1也就是下一次递归调用的情况下才会运行到了；既然可以代码复用省时省力为何不用呢！
代码：
public static List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);List<Integer> result=new ArrayList();List<List<Integer>> results=new ArrayList();combinationSum(candidates,0,target,result,results);return results;}public static void combinationSum(int[] candidates, int index,int target,List<Integer> result, List<List<Integer>> results) {if(index==candidates.length) {//have no item to selectreturn ;}if(candidates[index]>target) {// as same as last situation, which is mismatch conditionreturn ;}else if(candidates[index]==target) {//just right to get a result, which add to resultsList<Integer> resultFinal=new ArrayList<Integer>(result);resultFinal.add(candidates[index]);results.add(resultFinal);return ;//just for increasing appearance of code}else {//candidates[index]<target, get a candidate item add to result result.add(candidates[index]);//process candidate of index current by invoking next recursioncombinationSum(candidates,index , target-candidates[index], result, results);//remove last item for next recursion, just as backtrackingresult.remove(result.size()-1);//unneeded convey target-candidates[index] cause last line code:result.remove(results.size()-1);//this just as backtrackingcombinationSum(candidates,index+1 , target, result, results);}
}
Faster than 99.88% on leetcode
总结：
其实这次的提交能有faster than 99.88%还是有些许意外的（FT 100%是运用DFS实现的）。上面说到递归的资源损耗首先是体现在JVM程序栈的开辟上面，在本题中，每一次调用都需要复制一份相关传参数据副本（引用类型是引用类型值副本，在不同的栈帧上也指向同一堆空间地址，即其指向的数据对象还是一样的；但在某些情况下还是会开辟临时空间去存储这些数据，如String）；虽然有JIT的优化（现还不确定在递归情况下是否会采用内联策略，再挖个坑），但在不断的JVM栈帧移动中还是有了许多时间和空间上的损耗（相对于用自定义栈实现回溯），可能用递归实现最大的优点便是代码简洁便于理解了。
在最近的解题中发现经常遇到动态规划问题，动态规划是个好策略，相对于贪心算法，动态规划追求的是全局最优决策。看来是时候准备进入DP的学习了，关于回溯暂且先到这里吧。