网站备案的公司注销了,工程备案信息查询,成都住建局官网保租房,建设网站用户名1.问题描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复…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 302 candidates[i] 40candidates 的所有元素 互不相同1 target 40 难度等级 中等 题目链接 组合总和
2.解题思路 这道题是要我们找到候选数组中加起来等于目标和的所有数而且候选数组中的数可以重复使用。我们可以定义一个List集合来存储题目要的答案。因为数是可以重复使用的所以我们的基本思路就是从最小的数开始不断取出候选数来进行尝试选上一次已经选过的候选数也可以选比上一次的候选数还大的数。因此我们要先对候选数组进行排序这里排序还有一个好处就是如果我们已经获取到了目标和或者加上下一个候选数超过了目标和后续的候选数都可以不用进行尝试了因为后面的候选数都比当前的候选数大或者已经找到了。 //存储结果的List结合ListListInteger data new ArrayList();//对candidates进行排序方便后续进行剪枝操作Arrays.sort(candidates); 接着我们用一个递归函数来解决这个问题。 首先我们要确定一下递归的结束条件这里我用还需要寻找的目标数总和来判断如果还需要寻找的目标数为0说明我们刚好找到了和为target的组合如果小于0说明我们本次找的组合超过了target要舍去同时也不用往后找了直接返回就可以了。 //递归结束条件:找到目标和,将组合存入结果集合中,者还需要寻找的目标和小于0if(targetSum 0){data.add(new ArrayList(nums));return;}if(targetSum 0){return;} 接着我们要确定递归的参数。这里我们需要传入候选数组还需要寻找的目标和当前已经尝试到的目标数组的数据的索引index存储最终答案的list集合存储临时组合的List。 public void backtrack(int[] candidates,int targetSum,int index,ListListInteger data,ListInteger nums) 然后我们就可以来实现递归逻辑了。我们从当前数据的索引开始遍历候选数组这里我们可以做一个剪枝操作如果取出的数已经大于还需寻找的目标和则后续的候选数都可以不用尝试了一定会大于因为我们一开始就对数组进行排序了。接着将当前取出的数放入到临时组合中调用递归方法寻找以当前组合为子组合的所有组合这里需要注意的是我们传入的候选数组数据索引是最后一个被添加进去的数据的索引这样我们就可以实现重复选择当前数本身又不会重复使用比当前数小的数据导致出现排序不同但是每一个数出现次数相同的组合(不符合题意的)。找到以当前组合为子组合的所有组合之后要将临时组合中的当前数去掉(回溯)避免影响其他候选数的组合寻找。 //遍历candidates数组进行组合for(int i index;i candidates.length targetSum - candidates[i] 0;i){//添加到当前组合中nums.add(candidates[i]);//递归获取以当前组合为子组合的所有组合backtrack(candidates,targetSum-candidates[i],i,data,nums);//删除当前的候选数,避免影响后面的组合nums.removeLast();} 最后将存储结果的集合直接返回即可。
3.代码展示
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {//存储结果的List结合ListListInteger data new ArrayList();//对candidates进行排序方便后续进行剪枝操作Arrays.sort(candidates);//调用递归函数backtrack(candidates,target,0,data,new ArrayList());//返回结果return data;}public void backtrack(int[] candidates,int targetSum,int index,ListListInteger data,ListInteger nums){//递归结束条件:找到目标和,将组合存入结果集合中,者还需要寻找的目标和小于0if(targetSum 0){data.add(new ArrayList(nums));return;}if(targetSum 0){return;}//遍历candidates数组进行组合for(int i index;i candidates.length targetSum - candidates[i] 0;i){//添加到当前组合中nums.add(candidates[i]);//递归获取以当前组合为子组合的所有组合backtrack(candidates,targetSum-candidates[i],i,data,nums);//删除当前的候选数,避免影响后面的组合nums.removeLast();}}
}
4.总结 这道题容易做错的地方在于一不小心就会获取到重复的组合比如[2,2,3]和[2,3,2]这两个组合按照题意其实是一个组合所以我们每一层递归都要有一个起始索引来防止取到比最后一个取出的数要小的其他数。这道题我觉得是一道蛮不错的递归回溯题目挺有意思的。祝大家刷题愉快~
