java组合总和（力扣Leetcode39）
组合总和
力扣原题链接
问题描述
给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
示例
示例 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
输出: []
解题思路
这是一个典型的回溯算法问题。我们需要在给定的数字数组中寻找所有可能的组合，使其和等于目标数 target。
代码思路
- 初始化结果列表： 创建一个空的列表
result，用于存储最终的组合结果。 - 回溯搜索： 定义一个回溯函数
backtrack，其参数包括当前处理的索引start、当前的目标值target、当前的组合路径path。 - 结束条件： 如果当前目标值等于 0，说明找到了一个有效组合，将其加入结果列表，并返回。
- 选择列表： 候选数字数组中的所有数字。
- 遍历选择： 从当前处理索引
start开始遍历候选数字数组。 - 做出选择： 将当前数字加入路径，并更新目标值为
target - candidates[i]。 - 递归进入下一层： 递归调用回溯函数，传入新的索引
i和更新后的目标值。 - 撤销选择： 回溯到上一层时，将当前选择的数字从路径中删除。
Java解题
写法一
直接用target来减，return判断条件为target == 0
import java.util.*;class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();backtrack(candidates, target, 0, new ArrayList<>(), result);return result;}private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> result) {// 结束条件：如果目标值为 0，说明找到了一个有效组合，将其加入结果列表if (target == 0) {result.add(new ArrayList<>(path));return;}// 从当前处理索引开始遍历候选数字数组for (int i = start; i < candidates.length; i++) {// 做出选择：将当前数字加入路径，并更新目标值if (target - candidates[i] >= 0) {path.add(candidates[i]);// 递归进入下一层，传入新的索引和更新后的目标值backtrack(candidates, target - candidates[i], i, path, result);// 撤销选择：回溯到上一层时，将当前选择的数字从路径中删除path.remove(path.size() - 1);}}}
}
写法2
加入一个sum来收集当前path里的总和，return判断条件为sum = target
class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {List<Integer> path = new ArrayList<>();backstrack(candidates,target,0,0,path);return res;}public void backstrack(int[] candidates,int target,int index,int sum,List<Integer> path){if(sum == target){res.add(new ArrayList<>(path));return;}for( int i = index;i<candidates.length;i++){if(sum>target) return;if(candidates[i]>target) continue;path.add(candidates[i]);backstrack(candidates,target,i,sum+candidates[i],path);path.remove(path.size()-1);}}
}