每日一题 77组合(剪枝)

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

题目

77
给定两个整数 n 和 k,返回范围 [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文章来源地址https://www.toymoban.com/news/detail-719567.html

题解

选或不选

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> ans = new ArrayList<>();
    private int k;
    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        dfs(n);
        return ans;
    }
    private void dfs(int i) {
        //可以选的个数
        int d = k - path.size();
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (i > d) {
            dfs(i - 1);
        }
        path.add(i);
        dfs(i - 1);
        path.remove(path.size() - 1);
    }
}

答案视角

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> ans = new ArrayList<>();
    private int k;
    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        dfs(n);
        return ans;
    }
    private void dfs(int i) {
        int d = k - path.size();
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j >= d; j--) {
            path.add(j);
            dfs(j - 1);
            path.remove(path.size() - 1);
        }
    }
}

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

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

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

相关文章

  • 【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )

    图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略 : 深度优先搜索 DFS 广度优先搜索 BFS \\\" 深度优先搜索 \\\" 英文名称是 Depth First Search , 简称 DFS ; DFS 基本思想 : 访问第一个邻接结点 : 从 起始点 出发 , 该 起始点 可能有 若干 邻接结点 , 访问 第一个 邻接结点

    2024年02月02日
    浏览(46)
  • 【数据结构与算法】图的深度优先和广度优先遍历

    😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享Java相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页 ✨✨座右铭✨✨ : 坚持到底,决不放弃,是成功的保证,只要你不放弃,你就有机会,只要放弃的人,他肯定是不会成功的人。 图是一

    2024年02月02日
    浏览(57)
  • 【剪枝】【广度优先】【深度优先】488祖玛游戏

    【动态规划】458:可怜的小猪 剪枝 广度优先 深度优先 在这个祖玛游戏变体中,桌面上有 一排 彩球,每个球的颜色可能是:红色 ‘R’、黄色 ‘Y’、蓝色 ‘B’、绿色 ‘G’ 或白色 ‘W’ 。你的手中也有一些彩球。 你的目标是 清空 桌面上所有的球。每一回合: 从你手上的

    2024年01月22日
    浏览(39)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(63)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(50)
  • python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

    了解树/图的 深度遍历,宽度遍历 基本原理; 会使用python语言编写 深度遍历,广度遍历 代码; 掌握 拓扑排序算法 搜索引擎 提到搜索两个子,大家都应该会想到搜索引擎,搜索引擎的基本工作步骤; 网页爬取 — 数据预处理 — 排序 — 查询 第一步,网页爬取,非常重要,

    2024年01月20日
    浏览(48)
  • 递归专题训练详解(回溯,剪枝,深度优先)

    在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出

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

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

    2024年02月09日
    浏览(35)
  • 每日OJ题_DFS回溯剪枝⑨_力扣39. 组合总和(两种思路)

    目录 力扣39. 组合总和 解析代码1 解析代码2 39. 组合总和 LCR 081. 组合总和 难度 中等 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ,并以列表形式返回。你可以按  任意顺序

    2024年04月28日
    浏览(31)
  • day24 | 回溯算法基础、77. 组合

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

    2024年02月11日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包