Leetcode JAVA刷刷站（39）组合总和

一、题目概述

二、思路方向

为了解决这个问题，我们可以使用回溯算法来找到所有可能的组合，使得组合中的数字之和等于目标数 target。因为数组中的元素可以无限制地重复选择，所以在回溯过程中，我们不需要跳过已经选择的元素，而是可以从当前位置开始继续选择。

三、代码实现

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  public class Solution {  List<List<Integer>> result = new ArrayList<>();  public List<List<Integer>> combinationSum(int[] candidates, int target) {  Arrays.sort(candidates); // 对数组进行排序，有助于提前结束回溯  List<Integer> tempList = new ArrayList<>();  backtrack(candidates, target, 0, tempList);  return result;  }  private void backtrack(int[] candidates, int remain, int start, List<Integer> tempList) {  if (remain < 0) {  return; // 如果剩余需要达到的和已经是负数，则剪枝  }  if (remain == 0) {  result.add(new ArrayList<>(tempList)); // 如果剩余需要达到的和为0，则找到了一种符合条件的组合  return;  }  for (int i = start; i < candidates.length; i++) {  // 因为元素可以重复选择，所以我们不需要跳过已经选择过的元素  // 但可以通过排序和剪枝来避免不必要的搜索  if (i > start && candidates[i] == candidates[i - 1]) {  continue; // 跳过重复的元素，避免产生重复的组合  }  tempList.add(candidates[i]);  backtrack(candidates, remain - candidates[i], i, tempList); // 注意这里是从i开始，允许选择相同的数字  tempList.remove(tempList.size() - 1); // 回溯，撤销选择  }  }  public static void main(String[] args) {  Solution solution = new Solution();  int[] candidates = {2, 3, 6, 7};  int target = 7;  List<List<Integer>> combinations = solution.combinationSum(candidates, target);  for (List<Integer> combination : combinations) {  System.out.println(combination);  }  }  
}

执行结果：

四、小结

在这个解决方案中，我们首先对数组进行排序，这是为了在处理过程中能够更方便地进行剪枝和跳过重复元素。然后，我们使用一个递归函数 backtrack 来遍历所有可能的组合。在递归函数中，我们检查当前的和是否等于目标值，或者是否已经是负数（如果是负数则剪枝）。然后，我们遍历数组，从当前位置开始选择元素，并递归地调用 backtrack 函数，传入剩余需要达到的和、下一个开始的位置（允许选择相同的数字）、以及当前的组合列表。最后，在回溯过程中，我们需要撤销选择，以便尝试其他可能的组合。

注意，在这个解决方案中，我们使用了 List<List<Integer>> 来存储所有可能的组合，并且使用 ArrayList 作为内部的临时列表来构建每个组合。在找到一种符合条件的组合时，我们通过创建一个新的 ArrayList 实例来将其添加到结果列表中，以避免在后续的回溯过程中修改已经添加到结果列表中的组合。

结语