【力扣】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

题解

暴力思考:k 等于多少就是多少层循环。

//示例中k为2
int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {	
    	sout(i+" "+j);
   	}
}

//示例中k为3
int n = 100;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int u = j + 1; u <= n; n++) {
        	sout(i+" "+j+" "+u);
        }
    }
}

回溯

回溯法解决的问题都可以抽象为树形结构(N叉树)。

n 相当于树的宽度,k 相当于树的深度。图中每次搜索到了叶子节点,就找到了一个结果。
在这里插入图片描述

回溯法三步

  • 递归函数的返回值以及参数

  • 回溯函数终止条件

  • 单层搜索的过程

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}
import java.util.*;

public class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public void backtracking(int n, int k, int startIndex) {
        // 终止条件
        if (path.size() == k) {
            //存放结果
            result.add(new ArrayList<>(path));
            return;
        }

        //横向遍历
        for (int i = startIndex; i <= n; i++) {
            //处理节点
            path.add(i);
            //纵向搜索
            backtracking(n, k, i + 1);
            //回溯,撤销处理结果
            path.removeLast();
        }
    }
}

剪枝优化

在这里插入图片描述
剪枝的地方就在递归中每一层的for循环所选择的起始位置。如果 for 循环选择的起始位置之后的元素个数已经不足需要的元素个数,那么就没有必要搜索了。

  • 已经选择的元素个数:path.size();
  • 还需要的元素个数为: k - path.size();
  • 在集合 n 中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
import java.util.*;

public class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public void backtracking(int n  , int k, int startIndex) {
        // 终止条件
        if (path.size() == k) {
            //存放结果
            result.add(new ArrayList<>(path));
            return;
        }

        //横向遍历
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {// i为本次搜索的起始位置
            //处理节点
            path.add(i);
            //纵向搜索
            backtracking(n, k, i + 1);
            //回溯,撤销处理结果
            path.removeLast();
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/83403.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

中睿天下受邀参加第六届电力信息通信新技术大会并发表主题演讲

2023年8月9-11日&#xff0c;中国电力企业联合会科技开发服务中心以“加快数字化转型助力新型电力系统建设”为主题&#xff0c;在杭州举办2023年&#xff08;第六届&#xff09;电力信息通信新技术大会暨数字化发展论坛。 大会旨在加快推进“双碳”目标下的新型能源体系和新型…

复合 类型

字符串和切片 切片 切片的作用是允许你引用集合中部分连续的元素序列&#xff0c;而不是引用整个集合。 例如&#xff1a; let s String::from("hello world");let hello &s[0..5]; // 切片 [0,5) 等效于&s[..5] let world &s[6..11]; // 切片…

Python学习 -- 类对象从创建到常用函数

在Python编程中&#xff0c;类是一种强大的工具&#xff0c;用于创建具有共同属性和行为的对象。本篇博客将详细介绍Python中类和对象的创建&#xff0c;类的属性和方法&#xff0c;以及一些常用的类函数&#xff0c;通过丰富的代码例子来帮助读者深入理解。 一、类和对象的创…

STM32设置为I2C从机模式(HAL库版本)

STM32设置为I2C从机模式&#xff08;HAL库版本&#xff09; 目录 STM32设置为I2C从机模式&#xff08;HAL库版本&#xff09;前言1 硬件连接2 软件编程2.1 步骤分解2.2 测试用例 3 运行测试3.1 I2C连续写入3.2 I2C连续读取3.3 I2C单次读写测试 4 总结 前言 我之前出过一篇关于…

AI 绘画Stable Diffusion 研究(十)sd图生图功能详解-精美二维码的制作

免责声明: 本案例所用安装包免费提供&#xff0c;无任何盈利目的。 大家好&#xff0c;我是风雨无阻。 为了让大家更直观的了解图生图功能&#xff0c;明白图生图功能到底是干嘛的&#xff0c;能做什么事情&#xff1f;今天我们继续介绍图生图的实用案例-精美二维码的制作。 对…

倒计时动效

1. 效果 2. html <div class"count"><span>3</span><span>2</span><span>1</span> </div>3. css body {width: 100vw;height: 100vh;overflow: hidden;display: flex;justify-content: center;align-items: cente…

【Apollo】阿波罗自动驾驶技术:引领汽车行业革新

前言 Apollo (阿波罗)是一个开放的、完整的、安全的平台&#xff0c;将帮助汽车行业及自动驾驶领域的合作伙伴结合车辆和硬件系统&#xff0c;快速搭建一套属于自己的自动驾驶系统。 开放能力、共享资源、加速创新、持续共赢是 Apollo 开放平台的口号。百度把自己所拥有的强大、…

iTOP-RK3568开发板ubuntu环境下安装Eclipse

eclipse 是使用 Java 语言开发的&#xff0c;一个 Java 应用程序&#xff0c;这意味着 eclipse 只能运行在 Java虚拟机上。倘若没有安装 JDK&#xff08;Java Development Kit&#xff09;&#xff0c;即使在 ubuntu 上安装了 eclipse&#xff0c;也不能运行&#xff0c;所以要…

fastgpt构建镜像

1.把client目录复制到服务器 .next和node_modules文件夹不用上传到服务器 在服务器目录运行 docker build -t fastgpt:1.0.3 . 构建服务 再运行 docker ps 就可以看到容器了

easyexcel合并单元格底色

一、效果图 二、导出接口代码 PostMapping("selectAllMagicExport")public void selectAllMagicExport(HttpServletRequest request, HttpServletResponse response) throws IOException {ServiceResult<SearchResult<TestMetLineFe2o3Export>> result …

Java虚拟机(JVM):垃圾收集算法

目录 一、分代收集理论 二、标记-清除算法 三、标记-复制算法 四、标记-整理算法 一、分代收集理论 分代收集理论建立在两个分代假说之上&#xff1a; 1、弱分代假说&#xff1a;绝大多数对象都是朝生夕灭的。 2、强分代假说&#xff1a;熬过越多次垃圾收集过程的对象就…

mysql 、sql server trigger 触发器

sql server mySQL create trigger 触发器名称 { before | after } [ insert | update | delete ] on 表名 for each row 触发器执行的语句块## 表名&#xff1a; 表示触发器监控的对象 ## before | after : 表示触发的时间&#xff0c;before : 表示在事件之前触发&am…

JVM的元空间了解吗?

笔者近期在面试的时候被问到了这个问题&#xff0c;元空间也是Java8当时的一大重大革新&#xff0c;之前暑期实习求职的时候有专门看过&#xff0c;但是近期秋招的时候JVM相关的内容确实有点生疏了&#xff0c;故在此进行回顾。 结构 首先&#xff0c;我们应了解JVM的堆结构&a…

深入理解python虚拟机:程序执行的载体——栈帧

栈帧&#xff08;Stack Frame&#xff09;是 Python 虚拟机中程序执行的载体之一&#xff0c;也是 Python 中的一种执行上下文。每当 Python 执行一个函数或方法时&#xff0c;都会创建一个栈帧来表示当前的函数调用&#xff0c;并将其压入一个称为调用栈&#xff08;Call Stac…

docker学习(十五)docker安装MongoDB

什么是MongoDB? MongoDB 是一个开源的、面向文档的 NoSQL 数据库管理系统&#xff0c;它以高性能、灵活的数据存储方式而闻名。与传统的关系型数据库不同&#xff0c;MongoDB 采用了一种称为 BSON&#xff08;Binary JSON&#xff09;的二进制 JSON 格式来存储数据。它是一种非…

(详解踩坑)GIT版本回滚git stash、git reset、git reset --hard、git revert

目录 背景 一、&#xff08;git log、git reflog&#xff09;查看git提交日志及命令历史 1.1 git log&#xff08;提交日志&#xff09; 1.2 git reflog&#xff08;命令历史&#xff09; 二、git reset&#xff08;回退到指定的版本&#xff0c;并且保留更改&#xff09; …

IDEA启动报错【java.sql.SQLSyntaxErrorException: ORA-00904: “P“.“PRJ_NO“: 标识符无效】

IDEA报错如下&#xff1a; 2023-08-17 11:26:15.535 ERROR [egrant-biz,b48324d82fe23753,b48324d82fe23753,true] 24108 --- [ XNIO-1 task-1] c.i.c.l.c.RestExceptionController : 服务器异常org.springframework.jdbc.BadSqlGrammarException: ### Error queryin…

leetcode 542. 01 Matrix(01矩阵)

矩阵中只有0&#xff0c;1值&#xff0c;返回每个cell到最近的0的距离。 思路&#xff1a; 0元素到它自己的距离是0&#xff0c; 只需考虑1到最近的0是多少距离。 BFS. 先把元素1处的距离更新为无穷大。 0的位置装入queue。 从每个0出发&#xff0c;走上下左右4个方向&…

axios / fetch 实现 stream 流式请求

axios 是一个支持node端和浏览器端的易用、简洁且高效的http库。本文主要介绍 axios 如何实现 stream 流式请求&#xff0c;注意这里需要区分 node 环境和浏览器环境。 一、node端 代码演示&#xff1a; const axios require(axios);axios({method: get,url: http://tiven.c…

【C# 基础精讲】使用async和await进行异步编程

在C#中&#xff0c;使用async和await关键字进行异步编程是一种强大的工具&#xff0c;可以在不阻塞主线程的情况下执行耗时操作&#xff0c;提高程序的并发性和响应性。本文将深入探讨async和await的基本概念、使用场景、编码规范以及一些示例&#xff0c;以帮助您更好地理解如…
最新文章