顺德 网站设计,主题猫仿虎嗅wordpress,支付商城网站制作,开发公司移交物业协议书目录 题目
思路
剪枝优化
代码 题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的…目录 题目
思路
剪枝优化
代码 题目
给你一个 无重复元素 的整数数组 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
输出: []
思路
和前面的组合问题不同的是最后的结果集里的数字可以有重复比如target是4结果集可以是22 本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回
本题还需要startIndex来控制for循环的起始位置
对于组合问题什么时候需要startIndex呢
如果是一个集合来求组合的话就需要startIndex例如力扣77和216.
如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex例如力扣17
注意以上只是说求组合的情况如果是排列问题又是另一套分析的套路.
终止只有两种情况sum大于target和sum等于target。
剪枝优化 对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。
代码
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger resultnew ArrayList();
//最后的结果集Arrays.sort(candidates);
//剪枝操作先从小到大排序如果哪个数已经大于target了那就不用再继续往下了backTracking(result,new ArrayList(),candidates,target,0,0);return result;}public void backTracking(ListListInteger result,ListInteger path,int[] candidates,int target,int sum,int index){
//path保存叶子节点target目标值sum叶子节点的和index遍历的时候从哪个数开始if(sumtarget){//符合要求把叶子节点加入结果集result.add(new ArrayList(path));return;}for(int iindex;icandidates.length;i){if(sumcandidates[i]target) break;//大于了就不需要继续往下了剪枝path.add(candidates[i]);backTracking(result,path,candidates,target,sumcandidates[i],i);//最后一个数还是i因为他最后的结果集可以重复比如234选了2继续往下的时候还可以选2path.remove(path.size() - 1); // 回溯移除路径 path 最后一个元素}}
}
