LeetCode39题：组合总和（原创）

本文主要是介绍LeetCode39题：组合总和（原创），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同
1 <= target <= 40

【题目链接】. - 力扣（LeetCode）

【解题代码】

package dp;import java.util.*;public class CombinationSum {public static void main(String[] args) {//int[] candidates = {2, 3, 6, 7};int[] candidates = {1, 2, 3};System.out.println("开始计算。。。");long start = System.currentTimeMillis();List<List<Integer>> numLists = new CombinationSum().combinationSum(candidates, 4);System.out.println("运行时长：" + (System.currentTimeMillis() - start) + "ms");for (List<Integer> numList : numLists) {System.out.println(Arrays.toString(numList.toArray()));}}private List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> numLists = new ArrayList<>();List<Integer> numList = new ArrayList<>();doCombinationSum(candidates, 0, target, numList, numLists);return numLists;}private void doCombinationSum(int[] candidates, int n, int target, List<Integer> numList, List<List<Integer>> numLists) {if (target == 0) {numLists.add(new ArrayList<>(numList));} else if (n < candidates.length) {doCombinationSum(candidates, n + 1, target, numList, numLists);if (target >= candidates[n]) {numList.add(candidates[n]);doCombinationSum(candidates, n, target - candidates[n], numList, numLists);numList.remove(numList.size() - 1);}}}}

【解题思路】

看到此题描述，第一反应就是应该采用“回溯算法”：依次遍历数组candidates 里面数字，根据题意对当前索引i的数字做两种选择：

当前数字candidates[i]不加入候选队列：直接递归处理下一个索引数字i+1；
当前数字candidates[i]如果小于target，选择将其加入候选队列：将目标整数 target减去当前candidates[i]，因为数字可以重复选择，再次递归处理索引数字i；
目标整数 target为0,说明当前候选数字序列满足要求，添加到结果集，此趟递归结束
按照上述思路完成代码编写，提交LeetCode成功

【解题步骤】

定义一个回溯递归函数doCombinationSum，参数包括整数数组 candidates，当前索引值n,目标值target,当前候选数列numList，结果数列numLists：
```
private void doCombinationSum(int[] candidates, int n, int target, List<Integer> numList, List<List<Integer>> numLists)
```
如果目标值target为0，说明当前候选数字序列numList满足要求，添加到结果集numLists
```
if (target == 0) {numLists.add(new ArrayList<>(numList));
} 
```
如果数组遍历还没遍历完，首先选择不选择当前数字，直接递归处理下一个索引数字即可
```
} else if (n < candidates.length) {doCombinationSum(candidates, n + 1, target, numList, numLists);
```
接下来，如果当前数字小于等于目标值target，那么选择此数字，将此数字添加到候选数字序列，将目标值target去当前candidates[i]，并从当前索引重复递归，递归完毕，回溯将次数字从候选数字序列中删除
```
if (target >= candidates[n]) {numList.add(candidates[n]);doCombinationSum(candidates, n, target - candidates[n], numList, numLists);                numList.remove(numList.size() - 1);
}
```

【思考总结】

了解掌握回溯算法定义：回溯算法定义回溯算法，是一种选优搜索法，又称为试探法，按选优条件向前搜索以达到目标。回溯算法简要说：但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。而满足回溯条件的某个状态的点称为“回溯点”。
回溯与递归的区别：递归的基本性质就是函数调用，在处理问题的时候，递归往往是把一个大规模的问题不断地变小然后进行推导的过程。回溯则是利用递归的性质，从问题的起始点出发，不断地进行尝试，回头一步甚至多步再做选择，直到最终抵达终点的过程；
LeetCode解题之前，一定不要看题解，看了就“破功”了！

这篇关于LeetCode39题：组合总和（原创）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！