这个Java代码实现的是LeetCode上的“组合总和”（Combination Sum）问题，采用的是回溯算法（Backtracking）。下面是详细的算法思想解释：
算法思想：
-
回溯算法的基本思路：
回溯算法是一种通过递归搜索所有可能解的算法。它会尝试构建一个解（在这里是一个数的组合），如果当前构建的解不符合条件（即总和超过目标值），就会撤销之前的选择，返回上一层递归，继续尝试其他可能的解。 -
步骤详解：
- 你有一组候选数
candidates，目标是找到所有可以让它们的组合之和等于target的组合。 - 在回溯函数
backtrack()中：- 递归结束条件：
- 如果当前的
target为 0，说明找到了一个符合条件的组合，加入到结果集中。 - 如果
target小于 0，说明当前组合的总和超过了目标值，直接返回，放弃当前路径。
- 如果当前的
- 递归过程：
- 遍历
candidates数组中的每个数，从当前开始的位置i逐一尝试。因为题目允许同一个数字无限次使用，所以我们可以在递归调用时将i传入，而不是i + 1，这样就可以重复选择当前数字。 - 递归调用时，
target - candidates[i]表示我们减去当前选择的数字，继续递归寻找下一个可以加入的数字。 - 每次递归返回后，将当前选择的数字从当前组合
current中移除（即“回溯”），尝试其他可能的组合。
- 遍历
- 递归结束条件：
- 你有一组候选数
-
主要递归逻辑：
- 对于每一个候选数
candidates[i]，首先将其加入当前组合current，然后递归调用函数backtrack()，继续尝试构建新的组合。 - 如果找到了满足条件的组合（即
target == 0），则将当前组合加入到结果集中。 - 如果当前组合无效（即
target < 0），直接返回。 - 递归结束后，移除当前选中的数字（即回溯），以便继续尝试其他组合。
- 对于每一个候选数
代码关键点：
- 递归函数
backtrack()：这是整个回溯过程的核心。在这个函数中，我们尝试向当前组合中添加新的数字，并递归地去寻找下一步的可能解。 - 结果存储：通过递归逐步构建组合，当组合符合条件时，将其复制并添加到最终结果集中。
- 去重：因为允许同一个数字多次使用，所以每次递归时，从当前数字
i开始继续往后搜索，而不是重新从头开始。
总结：
该算法的复杂度取决于输入数组 candidates 的大小以及目标值 target。由于每个数字可以被多次使用，回溯算法会生成大量可能的组合，然后通过递归逐一验证。这种方法虽然可能会有较高的时间复杂度，但可以保证找到所有合法的组合。
java solution
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), candidates, target, 0);return result;}private void backtrack(List<List<Integer>> result, List<Integer> current, int[] candidates, int target, int start) {if(target == 0) {result.add(new ArrayList<>(current));//result.add(current); return;}if(target < 0) {return;}for(int i = start; i < candidates.length; ++i) {//添加当前元素current.add(candidates[i]);backtrack(result, current, candidates, target - candidates[i], i);//删除当前元素current.remove(current.size() - 1); //按照下标移除元素。}}
}
这一行代码中result.add(new ArrayList<>(current));为什么需要使用new，而不是result.add(current); ?
这是一个非常好的问题！让我为你详细解释一下为什么在这行代码中需要使用 new ArrayList<>(current)，而不是直接使用 result.add(current)。
原因：
当你在 result.add(current) 中直接添加 current 时，实际上是将当前列表 current 的引用添加到 result 中，而不是添加一个新创建的列表。这样做会导致一个引用问题：因为 current 是一个动态变化的列表，后续对 current 的修改会影响已经添加到 result 中的组合。
具体问题如下：
- 假设你有一个
current列表，并且你在回溯过程中不断修改它，比如通过current.add()和current.remove()。 - 如果你在
result.add(current)中直接添加current，其实添加的是它的引用，这意味着result中的每个组合实际上都是指向同一个current列表。 - 当你继续回溯并修改
current时，所有在result中已经添加的组合也会同步发生变化，因为它们指向的是同一个对象。
new ArrayList<>(current) 的作用：
为了避免这个问题，我们需要在将 current 添加到 result 时创建一个当前列表的副本。具体来说，new ArrayList<>(current) 会创建一个新的 ArrayList，并将 current 列表的所有元素复制到这个新列表中。这样一来，result 中的每个组合都是一个独立的列表，它们不会受到后续 current 列表修改的影响。
举例说明：
假设在某个时刻，current 是 [2, 3]，并且你使用 result.add(current) 添加它到 result，然后在回溯过程中，你又继续修改 current 变成 [2, 3, 7]。如果你没有创建 current 的副本，那么 result 中存储的也会变成 [2, 3, 7]，这显然是不正确的，因为你之前想要存储的是 [2, 3]。
然而，如果你使用 result.add(new ArrayList<>(current))，在添加 [2, 3] 时，result 会保存这个列表的副本，后续你修改 current 时，它不会影响到已经保存的组合。
小结：
result.add(current)添加的是current的引用，后续对current的修改会影响result中的内容。result.add(new ArrayList<>(current))创建了current的副本，从而确保每次添加到result中的是当前组合的快照，不会被后续的修改影响。
这个技巧在回溯算法中非常常见，因为回溯过程中我们通常会动态修改路径（组合），因此需要保存路径的副本以避免引用问题。
