【LeetCode】39.组合总和

这篇具有很好参考价值的文章主要介绍了【LeetCode】39.组合总和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

给你一个 无重复元素 的整数数组 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 <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

解答

源代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> arr = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();

        dfs(candidates, target, arr, combine, 0);

        return arr;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> arr, List<Integer> combine, int index) {
        if (index == candidates.length) {
            return;
        }

        if (target == 0) {
            System.out.println(combine);
            arr.add(new ArrayList<Integer>(combine));
            return;
        }

        // 跳过当前的数
        dfs(candidates, target, arr, combine, index + 1);

        if (target - candidates[index] >= 0) {
            combine.add(candidates[index]);
            dfs(candidates, target - candidates[index], arr, combine, index);
            combine.remove(combine.size() - 1);
        }
    }
}

总结

努力理解回溯(深度优先遍历)算法中……文章来源地址https://www.toymoban.com/news/detail-604144.html

到了这里,关于【LeetCode】39.组合总和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode(力扣)39. 组合总和Python

    https://leetcode.cn/problems/combination-sum/description/

    2024年02月09日
    浏览(35)
  • leetcode216. 组合总和 III(回溯算法-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combination-sum-iii 找出所有相加之和为 n 的 k 个数的组合,且满足下列条件: 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。 示例 1: 输

    2024年02月10日
    浏览(45)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(40)
  • 【Leetcode】377. 组合总和 Ⅳ

    题目链接🔗 给你一个由 不同 整数组成的数组 n u m s nums n u m s ,和一个目标整数 t a r g e t target t a r g e t 。请你从 n u m s nums n u m s 中找出并返回总和为 t a r g e t target t a r g e t 的元素组合的个数。 题目数据保证答案符合 32 32 32 位整数范围。 示例 1: **输入:**nums = [1,2,3],

    2024年04月23日
    浏览(38)
  • LeetCode-216-组合总和Ⅱ

    题目链接: LeetCode-216-组合总和Ⅱ 解题思路:回溯算法 注意事项注释中有 代码实现:

    2024年02月09日
    浏览(43)
  • LeetCode 377. 组合总和 Ⅳ

    解题思路 之前一直以为这是背包问题,后来发现,这个是有顺序的, 而背包问题是无序的,但是我们也可以用dp分析法来分析。 相关代码

    2024年04月12日
    浏览(43)
  • 【LeetCode:216. 组合总和 III + 递归】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年04月25日
    浏览(52)
  • 40. 组合总和 II - 力扣(LeetCode)

    题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 输入示例 输出示例 解题代码

    2024年01月23日
    浏览(39)
  • Leetcode—216.组合总和III【中等】

    之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

    2024年01月23日
    浏览(42)
  • 【LeetCode-中等题】40. 组合总和 II

    本题需要注意的就是去重操作因为nums数组里面的元素可能存在重复: 不重复的版本:【LeetCode-中等题】39. 组合总和 不去重版 参考讲解视频—回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II

    2024年02月09日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包