今天我们来看一下 LeetCode 36：组合总和，这道题目和对应的解法。
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
代码语言：javascript复制输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 2 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
在深入解析之前，了解一些基础概念是很重要的：
- 回溯算法：一种通过探索所有可能的候选解来找出所有解的方法，如果候选解被证明不是一个解（或者至少不是最后一个解），回溯算法会丢弃它，并回退到之前的步骤，尝试其他的候选解。
- 递归：方法或函数在其定义或说明中调用自身的一种程序设计技巧。
问题描述
“组合总和”问题要求我们找出所有可以使数字总和等于给定目标数的组合，这些组合是从给定的一个无重复元素数组中选择出来的。同一个数字可以无限次地被选取。
代码解析
类和全局变量
Solution：类名称。List<List<Integer>> res：用来存储所有可能的组合。
方法 combinationSum
- 参数：一个整数数组
candidates和一个目标数target。 - 功能：初始化路径（
path）并开始回溯。 - 返回：所有可能使得和等于
target的组合。
方法 backtrack
- 参数：
nums（候选数字数组），target（目标数），path（当前路径），start（探索的起始位置）。 - 功能：执行回溯算法的核心逻辑。
回溯算法的核心步骤
- 结束条件：
- 如果
target < 0，说明当前路径不可能形成解，返回。 - 如果
target == 0，找到一个有效组合，将其加入结果中。
- 如果
- 选择列表：
- 使用
for循环从start开始选择候选数字，确保数字不会重复选取。
- 使用
- 做出选择：
- 将当前数字
nums[i]添加到路径中。
- 将当前数字
- 递归调用：
- 递归地调用
backtrack，目标值减去当前数字nums[i]，同时start设置为当前索引i。
- 递归地调用
- 撤销选择：
- 从路径中移除最后添加的数字，回溯到之前的状态。
解题思路
- 初始化一个空路径和结果列表。
- 从第一个数字开始，逐个尝试将
candidates中的数字加入路径。 - 如果加入一个数字后，路径和等于目标值，则将该路径加入结果列表。
- 如果路径和小于目标值，继续添加更多的数字。
- 如果路径和超过目标值，放弃该路径，尝试其他选择。
- 使用递归和回溯来遍历所有可能的路径。
示例
假设 candidates = [2, 3, 6, 7] 且 target = 7，我们的目标是找出所有组合，使得各个数字的和为 7。可能的组合包括 [2, 2, 3] 和 [7]。
总结
通过递归和回溯，我们可以有效地探索所有可能的组合，找到所有使数字总和等于目标值的组合。代码中的每个步骤都是为了维护当前路径的状态，确保所有可能的组合都被探索到。
参考代码：
代码语言：javascript复制// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
backtrack( candidates , target , path , 0 );
return res;
}
// 1、画出递归树，找到状态变量(回溯函数的参数)
// start 表示递归时正在访问的数组元素下标
// nums 表示当前集合中的元素
// target 表示想在当前区间拼凑出的目标值
// path 表示选择的路径
private void backtrack(int[] nums,int target,List<Integer> path,int start) {
// 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
if (target < 0) {
// 一些逻辑操作（可有可无，视情况而定）
// 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
return;
}
if(target == 0 ){
// 找到一个组合了
res.add(new ArrayList(path));
return;
}
// 3、确定选择列表，即需要把什么数据存储到结果里面
// for 循环就是一个选择的过程
// i 等于 start 表示，后续可以选的元素一开始只能从 start 开始
// 比如 nums = [2,3,6,7]
// i = 1，指向了元素 3 ，表示当前后续选择的过程中，只能从 3 开始选，可以重复选 3 ，但无法选 2 了
// i = 2，指向了元素 6 ，表示当前后续选择的过程中，只能从 6 开始选，可以重复选 6 ，但无法选 2、3 了
for (int i = start ; i < nums.length ; i ) {
// 当前路径上可以把 nums[i] 加上
path.add(nums[i]);
// 一些逻辑操作（可有可无，视情况而定）
// 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
// 需要剪枝
// 此时，目标值 target，已经从 target 变成了 target - nums[i]
// 接下来需要去【某个区间中】拼凑 target - nums[i]
// 由于 同一个 数字可以 无限制重复被选取
// 当前正在使用 nums[i]，那么为了拼凑 target - nums[i]，依旧可以继续从使用 nums[i] 开始
// 而 i 前面的元素，比如 num[i-1]、 num[i-2]无法继续使用，实现了剪枝操作
int nowposition = i ;
// 5、做出选择，递归调用该函数，进入下一层继续搜索
// 递归
backtrack(nums, target - nums[i] , path , nowposition );
// 一些逻辑操作（可有可无，视情况而定）
// 6、撤销选择，回到上一层的状态
path.remove(path.size()-1);
}
}
}
