当前位置：首页 > news >正文

力扣经典算法篇-44-组合总和(回溯问题）

news 2025/8/7 5:45:24

1、题干

给你一个无重复元素的整数数组candidates和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：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

2、解题

求所有组合的问题通常可以使用回溯算法就行求解。

回溯的基本实现步骤：
找到固定不变的量，每趟递归动态变化的量，结果集。
递归一定要有终止条件，终止条件要校验和添加结本趟结果到结果集合中。
循环递归，注意要先添加元素向前递归，之后进行回退操作；怎么添加的元素进行向后递归，就要怎么删除元素向前回溯。

方法一：（回溯法–结果校验处理）

利用回溯法的解答模版，可以获取所有可用排列的结果，但是可能造成重复问题。如：（2，2，3）和（2，3，2）实际上是想通过的结果。
所以保存结果时，需要校验是否重复，重复数据不能再次添加到结果集。

代码示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Test50 {public static List<List<Integer>> combinationSum(int[] candidates, int target) {// 不变的结果集List<List<Integer>> result = new ArrayList<>();// 每趟变量可变的元素// 每趟添加的元素List<Integer> tempList = new ArrayList<>();// 添加元素的下标int index = 0;// 当前趟的结果和int sum = 0;// 递归（不变的：目标数组candidates，目标值target； 每趟变化的：临时数组tempList，添加元素下标index，每一趟当前和sum； 结果集）goAndBack(candidates, target, tempList, index, sum, result);return result;}private static void goAndBack(int[] candidates, int target, List<Integer> tempList, int index, int sum, List<List<Integer>> result) {if (sum >= target) {// 大于等于目标值时，可以结束当前趟遍历if (sum == target) {// 当前趟元素排序后校验结果集是否存在，不存在可以添加到结果集ArrayList<Integer> oneGoal = new ArrayList<>(tempList);Collections.sort(oneGoal);if (!result.contains(oneGoal)){result.add(oneGoal);}}// 结果本趟递归，向前回溯return;}for (int i = 0; i < candidates.length; i++) {    // 因为元素可以重复添加，所以这里每次都从0号位置开始添加// 添加元素，计算和，向后递归tempList.add(candidates[i]);sum = sum + candidates[i];goAndBack(candidates, target, tempList, index + 1, sum + candidates[i], result);// 删除添加的元素，减去当前值，向前回溯sum = sum - candidates[i];tempList.remove(index);   // 或tempList.remove(tempList.size()-1); }}public static void main(String[] args) {int[] candidates = {2, 3, 6, 7};int target = 7;System.out.println(combinationSum(candidates, target));}
}

方法二：（回溯法–指定遍历的起始位置）

上面的方法一中，每次都是从位置0开始遍历添加元素，直到符合条件为止，相对而言，递归和回溯的次数都比较多。
可以换一种方式，在向后递归的时候，指定起始遍历的位置，即：下一次对的起始位置也是本次递归的起始位置，不是从0开始。这样就在遍历组装结果的过程中避免了重复的可能，减少遍历和比较的次数，效率更高。

代码示例：

 public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>();List<Integer> temp = new ArrayList<>();dfs(ans, temp, 0, 0, candidates, target);return ans;}public void dfs(List<List<Integer>> ans, List<Integer> temp, int index, int sum, int[] candidates, int target) {if (sum >= target) {if (sum == target) {ans.add(new ArrayList<>(temp));}return;}for (int i = index; i < candidates.length; i++) {// 添加元素，向后递归temp.add(candidates[i]);dfs(ans, temp, i, sum + candidates[i], candidates, target);     // 下一次遍历的位置i，最小也是index，避免过度回溯// 删除元素，向前回溯temp.remove(temp.size() - 1);}}