LeetCode-77-组合

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

LeetCode-77-组合,算法,leetcode,算法

一:题目描述:

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

二:示例与提示

示例 1:
输入:n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2:
输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

三:思路

回溯+剪枝

对于这类组合问题,可以将题目所描述的数组通过组合去构建一个树形结构

LeetCode-77-组合,算法,leetcode,算法

  • 横向拓展是数组中的元素个数,从1到n
  • 纵向拓展是深度,是对应元素的组合
  • 通过不断的递归和回溯,在每一层次中构建组合,搜索到对应的叶子节点
  • 图中每次搜索到了叶子节点,我们就找到了一个结果,将结果收集到结果集中即可

四:代码 + 复杂度分析

回溯+剪枝
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    //回溯
    //确定回溯函数的参数
    //存放最终所有结果的数组
    const res = []
    //path单层结果
    const path = []
    const backtracking = (n, k, index) => {
        //终止条件
        if(path.length === k) {
            console.log(path)
            //收集结果
            res.push([...path])
            return 
        }
        //单层逻辑
        for(let i = index; i <= n - (k - path.length) + 1; i++) {
            //路径收集
            path.push(i)
            //递归
            backtracking(n, k, i + 1)
            // console.log(path)
            //回溯
            path.pop()
        }
    }
    backtracking(n, k, 1)
    return res
};
  • 时间复杂度:O(C(n, k))

    • 对于每个数字,我们有两个选择(包括或不包括),并且我们有k个选择(需要选择k个数字)
    • 其中C(n, k)表示从n个元素中选择k个元素的组合数,也可以表示为二项式系数
  • 空间复杂度:O(k + 2^n)文章来源地址https://www.toymoban.com/news/detail-701668.html

    • 总的空间复杂度是 O(k + 2^n),其中 k 反映了递归树的深度,而 2^n 反映了结果数组 res 的可能长度

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

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

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

相关文章

  • LeetCode:77. 组合——回溯法,是暴力法?

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 来源:力扣(LeetCode) 难度: 中等 提示: 1 = n = 20 1 = k = n 示例 1: 输入:

    2023年04月18日
    浏览(30)
  • 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算法题解(回溯)|39. 组合总和、40. 组合总和 II、131. 分割回文串

    题目链接:39. 组合总和 题目描述: 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数

    2024年02月05日
    浏览(58)
  • 【回溯算法】77. 组合

    回溯结束条件 track长度等于k 然后收集当前的路径 遍历所有的节点 然后选择当前节点 通过start参数控制遍历 避免产生重复的子集 移除当前的选择

    2024年02月09日
    浏览(35)
  • day24 | 回溯算法基础、77. 组合

    目录: 回溯法理论基础 https://programmercarl.com/回溯算法理论基础.html#题目分类大纲如下 回溯法,一般可以解决如下几种问题: 组合问题:N个数里面按一定规则找出k个数的集合 切割问题:一个字符串按一定规则有几种切割方式 子集问题:一个N个数的集合里有多少符合条件的

    2024年02月11日
    浏览(39)
  • 【Leetcode60天带刷】day27回溯算法——39. 组合总和,40.组合总和II,131.分割回文串

    ​ 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限制重复

    2024年02月11日
    浏览(45)
  • 稀碎从零算法笔记Day45-LeetCode:电话号码的字母组合

    题型:映射、回溯算法、递归 链接:17. 电话号码的字母组合 - 力扣(LeetCode) 来源:LeetCode 给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例

    2024年04月11日
    浏览(40)
  • 力扣日记1.21-【回溯算法篇】77. 组合

    日期:2023.1.21 参考:代码随想录、力扣 终于结束二叉树了!听说回溯篇也是个大头,不知道这一篇得持续多久了…… 题目描述 难度:中等 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入:n = 4, k = 2 输出:

    2024年01月22日
    浏览(59)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包