万网网站备案证书,鲜花网站建设目的,景观建筑人才网,东莞微网站建设报价题目#xff1a;
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限…题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
思路
全局变量result存储结果集path存储某一组合
第一步确定参数与返回值。参数为candidates数组targetsumpath数组中现有值之和startIndex遍历的candidates数组下标起始无返回值
第二步确定终止条件。当targetsum时获取到一个组合将组合加入到结果集中
第三步确定单层递归逻辑。for循环遍历candidates数组从startIndex到candidates数组的最后一个元素。进行剪枝优化操作当sumcandidates[i]target时就不必进行下去了。for循环里的步骤就是更新sum更新path递归调用回溯。
代码 ListListInteger resultnew ArrayList();//结果集ListInteger pathnew ArrayList();//存储某一组合public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backTracking(candidates,target,0,0);return result;}public void backTracking(int[] candidates,int target,int sum,int startIndex){if(sumtarget){result.add(new ArrayList(path));return;}for(int istartIndex;icandidates.lengthsumcandidates[i]target;i){sumcandidates[i];path.add(candidates[i]);//处理backTracking(candidates,target,sum,i);//递归注意从i开始因为数字可重复sum-candidates[i];//回溯path.remove(path.size()-1);}}
