东莞网站推广哪家好,wordpress自动回到顶部,网站建设需要摊销多久,企业网站建设难吗组合总和
力扣原题链接
问题描述
给定一个无重复元素的整数数组 candidates 和一个目标整数 target#xff0c;找出 candidates 中可以使数字和为目标数 target 的所有不同组合#xff0c;并以列表形式返回。你可以按任意顺序返回这些组合。
示例
示例 1#xff1a;
输…组合总和
力扣原题链接
问题描述
给定一个无重复元素的整数数组 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 ListListInteger combinationSum(int[] candidates, int target) {ListListInteger result new ArrayList();backtrack(candidates, target, 0, new ArrayList(), result);return result;}private void backtrack(int[] candidates, int target, int start, ListInteger path, ListListInteger 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 {ListListInteger res new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {ListInteger path new ArrayList();backstrack(candidates,target,0,0,path);return res;}public void backstrack(int[] candidates,int target,int index,int sum,ListInteger path){if(sum target){res.add(new ArrayList(path));return;}for( int i index;icandidates.length;i){if(sumtarget) return;if(candidates[i]target) continue;path.add(candidates[i]);backstrack(candidates,target,i,sumcandidates[i],path);path.remove(path.size()-1);}}
}
