本文主要是介绍LeetCode--39. Combination Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://leetcode.com/problems/combination-sum/
这是一个组合和的问题，备选数组里的数不重复，但是可以选择相同的数。肯定要用到回溯（backtrace）递归的方法。
我写递归时喜欢用一个静态list来存最终返回的答案，再开一个较大的静态数组来存临时答案。
下面考虑递归函数怎么写，被选数组和目标和肯定是一直要带的参数，需要一个idx变量来标记某次递归函数调用时在原数组中搜索的起点，这里因为可以重复选，因此起点可以在下一次递归函数调用时重复取到。还有因为存储在静态数组中的有效答案需要一个变量来记录，并随着数组向后搜索调用递归函数时自动增加。具体代码如下：
class Solution {public static List<List<Integer>> ret;public static int[] record=new int[100000];public static List<List<Integer>> combinationSum(int[] candidates, int target){ret=new LinkedList<>();recursive(candidates,0,target,0);return ret;}public static void recursive(int[] candidates,int idx,int target,int length){if(target==0){LinkedList<Integer> tmp=new LinkedList();for(int i=0;i<length;i++)tmp.add(record[i]);ret.add(tmp);return;}if(target<0 || idx>=candidates.length)return;for(int i=idx;i<candidates.length;i++){record[length]=candidates[i];recursive(candidates,i,target-candidates[i],length+1);}}
}
这篇关于LeetCode--39. Combination Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
