Leetcode 组合总和

这个Java代码实现的是LeetCode上的“组合总和”（Combination Sum）问题，采用的是回溯算法（Backtracking）。下面是详细的算法思想解释：

算法思想：

1. 回溯算法的基本思路：
   回溯算法是一种通过递归搜索所有可能解的算法。它会尝试构建一个解（在这里是一个数的组合），如果当前构建的解不符合条件（即总和超过目标值），就会撤销之前的选择，返回上一层递归，继续尝试其他可能的解。

2. 步骤详解：

   • 你有一组候选数 candidates，目标是找到所有可以让它们的组合之和等于 target 的组合。
   • 在回溯函数 backtrack() 中：
     • 递归结束条件：
       • 如果当前的 target 为 0，说明找到了一个符合条件的组合，加入到结果集中。
       • 如果 target 小于 0，说明当前组合的总和超过了目标值，直接返回，放弃当前路径。
     • 递归过程：
       • 遍历 candidates 数组中的每个数，从当前开始的位置 i 逐一尝试。因为题目允许同一个数字无限次使用，所以我们可以在递归调用时将 i 传入，而不是 i + 1，这样就可以重复选择当前数字。
       • 递归调用时，target - candidates[i] 表示我们减去当前选择的数字，继续递归寻找下一个可以加入的数字。
       • 每次递归返回后，将当前选择的数字从当前组合 current 中移除（即“回溯”），尝试其他可能的组合。

3. 主要递归逻辑：

   • 对于每一个候选数 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 中的是当前组合的快照，不会被后续的修改影响。

这个技巧在回溯算法中非常常见，因为回溯过程中我们通常会动态修改路径（组合），因此需要保存路径的副本以避免引用问题。