北京移动端网站,济南网站建设技术支持,网站收录工具,绍兴优秀做网站的跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode#xff1a;39. 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 cand… 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode39. 组合总和 给你一个 无重复元素 的整数数组 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 输出: [] 本题里面candidates是可以重复的在进入递归函数的时候传递的参数是i上一题不能重复传递的是i1 public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates);ListListInteger res new ArrayList();backtracking(candidates, target, 0, 0, new ArrayList(), res);return res;}private void backtracking(int[] candidates, int target, int index, int sum, ListInteger path,ListListInteger res) {if (sum target) {res.add(new ArrayList(path));return;}for (int i index; i candidates.length; i) {if (sum candidates[i] target)break;path.add(candidates[i]);// 注意因为数字可以重复所以递归函数中传递的还是ibacktracking(candidates, target, i, sum candidates[i], path, res);path.removeLast();}}
