当前位置: 首页 > news >正文

力扣第 77 题 组合

题目描述

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

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

示例

示例 1

输入

n = 4, k = 2

输出

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
示例 2

输入

n = 1, k = 1

输出

[[1]]

解题思路

1. 回溯法

回溯法是解决组合问题的经典方法,通过递归构建所有可能的组合。

算法步骤

  1. 定义一个函数 backtrack(start, path),其中 start 表示搜索的起点,path 是当前构建的组合。
  2. 如果当前组合 path 的长度等于 k,将其加入结果集中。
  3. 遍历从 startn 的所有数字:
    • 将当前数字加入组合。
    • 递归构建下一个数字的组合。
    • 回溯,移除当前数字。

回溯法的时间复杂度是 O(C(n, k)),其中 C ( n , k ) = n ! k ! ( n − k ) ! C(n, k) = \frac{n!}{k!(n-k)!} C(n,k)=k!(nk)!n!


实现代码

C语言实现
#include <stdio.h>
#include <stdlib.h>// 动态数组结构
typedef struct {int** data;int size;int capacity;
} Array;void initArray(Array* arr, int capacity) {arr->data = (int**)malloc(sizeof(int*) * capacity);arr->size = 0;arr->capacity = capacity;
}void addToArray(Array* arr, int* combination, int k) {if (arr->size == arr->capacity) {arr->capacity *= 2;arr->data = (int**)realloc(arr->data, sizeof(int*) * arr->capacity);}arr->data[arr->size] = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++) {arr->data[arr->size][i] = combination[i];}arr->size++;
}void backtrack(int n, int k, int start, int* combination, int combSize, Array* result) {if (combSize == k) {addToArray(result, combination, k);return;}for (int i = start; i <= n; i++) {combination[combSize] = i;backtrack(n, k, i + 1, combination, combSize + 1, result);}
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {Array result;initArray(&result, 16);int* combination = (int*)malloc(sizeof(int) * k);backtrack(n, k, 1, combination, 0, &result);*returnSize = result.size;*returnColumnSizes = (int*)malloc(sizeof(int) * result.size);for (int i = 0; i < result.size; i++) {(*returnColumnSizes)[i] = k;}free(combination);return result.data;
}int main() {int n = 4, k = 2;int returnSize;int* returnColumnSizes;int** combinations = combine(n, k, &returnSize, &returnColumnSizes);printf("Combinations:\n");for (int i = 0; i < returnSize; i++) {printf("[");for (int j = 0; j < returnColumnSizes[i]; j++) {printf("%d", combinations[i][j]);if (j < returnColumnSizes[i] - 1) printf(", ");}printf("]\n");free(combinations[i]); // 释放每个组合的内存}free(combinations); // 释放结果数组的内存free(returnColumnSizes); // 释放列大小数组的内存return 0;
}

代码解析

  1. 动态数组

    • 使用 Array 结构来动态存储组合结果。
    • initArray 初始化数组,addToArray 动态增加组合。
  2. 回溯函数

    • backtrack 函数递归构建所有可能的组合。
    • 使用 start 控制数字范围,避免重复组合。
  3. 主函数

    • combine 是主函数,调用回溯并返回结果。
    • 动态分配 returnColumnSizes 以存储每个组合的列数。
  4. 内存管理

    • 在主函数中释放动态分配的内存,避免内存泄漏。

时间复杂度和空间复杂度

  • 时间复杂度

    • 回溯构造所有组合的复杂度是 O(C(n, k)),即 n ! k ! ( n − k ) ! \frac{n!}{k!(n-k)!} k!(nk)!n!
  • 空间复杂度

    • 临时数组 combination 的空间复杂度为 O(k)
    • 存储结果的空间复杂度为 O ( C ( n , k ) ⋅ k ) O(C(n, k) \cdot k) O(C(n,k)k)

相关文章:

力扣第 77 题 组合

题目描述 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按任意顺序返回答案。 示例 示例 1 输入&#xff1a; n 4, k 2输出&#xff1a; [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]示例 2 输入&#xff1a; n 1, k …...

(超详细图文)PLSQL Developer 配置连接远程 Oracle 服务

1、下载配置文件 &#xff08;超详细图文详情&#xff09;Navicat 配置连接 Oracle-CSDN博客 将下载的文件解压到单独文件夹&#xff0c;如&#xff1a;D:\App\App_Java\Oracle\instantclient-basic-windows.x64-19.25.0.0.0dbru 2、配置 打开 PLSQL Developer&#xff0c;登…...

元器件选型与参数13 电源的分类-线性电源参数 RT9013 AMS1117 PCB布局布线

目录 一、线性电源 1、重要参数 2、线性电源效率一定低吗 3、线性电源并联扩流 4、常见电路 RT9013-LDO AMS1117-xx-LDO 5、布局布线 6、外置输入与电池供电 7、单片机控制其他模组供电实现低功耗 二、开关电源与线性电源配合 1、高效率与低噪声 DC-DC电源大致分为…...

RHEL7+Oracle11.2 RAC集群-多路径(multipath+udev)安装步骤

RHEL7Oracle11.2RAC集群-多路径&#xff08;multipathudev&#xff09;安装 配置虚拟存储 使用StarWind Management Console软件&#xff0c;配置存储 dggrid1: 1g*3 Dggrid2: 1g*3 Dgsystem: 5g*1 系统表空间&#xff0c;临时表空间&#xff0c;UNDO&#xff0c;参数文件…...

每日速记10道java面试题03

其他资料 每日速记10道java面试题01-CSDN博客 每日速记10道java面试题02-CSDN博客 目录 一、你使用过java的反射机制吗&#xff1f;如何应用反射&#xff1f; 二、什么是泛型&#xff1f;泛型的作用是什么&#xff1f; 三、java的泛型擦除是什么&#xff1f; 四、Java 中…...

Vue 3 的双向绑定原理

Vue 3 的双向绑定原理是基于 响应式系统 和 数据劫持 技术来实现的。在 Vue 3 中&#xff0c;双向绑定通常是通过 v-model 指令来完成的&#xff0c;它本质上是数据的双向同步&#xff1a;当数据改变时&#xff0c;视图自动更新&#xff0c;反之&#xff0c;视图的修改也会更新…...

如何使用 Chrome 无痕浏览模式访问网站?

无痕浏览&#xff08;Incognito Mode&#xff09;是 Google Chrome 浏览器提供的一种隐私保护功能&#xff0c;它允许用户在一个独立的会话中浏览网页&#xff0c;而不会记录用户的浏览历史、下载历史、表单数据等。这对于希望保护个人隐私或进行临时性匿名浏览的用户来说非常有…...

Idea 2024.3 突然出现点击run 运行没有反应,且没有任何提示。

写这篇文章的目的是为了提供一个新的解决思路&#xff0c;因为存在同病不同原因。 如果你进行了1. 检查运行配置 (Run Configuration) 2. 清理和重建项目 3. 清除缓存并重启 IDEA 4.排除kotlin 5.重装idea等等操作之后仍然没有解决&#xff0c;可以试着按一下步骤进行解决。 检…...

【小白学机器学习36】关于独立概率,联合概率,交叉概率,交叉概率和,总概率等 概念辨析的例子

目录 1 先说结论 2 联合概率 3 边缘概率 4 (行/列)边缘概率的和 总概率1 5 条件概率 5.1 条件概率的除法公式 5.2 条件概率和联合概率区别 1 先说结论 关于独立概率&#xff0c;联合概率&#xff0c;交叉概率&#xff0c;交叉概率和&#xff0c;总概率 类型含义 …...

Spring Boot 项目——分层架构

在创建一个 Spring Boot 项目时&#xff0c;为了提高代码的可维护性、可扩展性和清晰度&#xff0c;通常会按照一定的分层架构进行设计。常见的分层架构包括以下几层&#xff1a; 1. Controller 层&#xff08;Web 层&#xff09; 作用&#xff1a;接收用户请求&#xff0c;并…...

wordpress网站首页底部栏显示网站备案信息

一、页脚文件footer.php 例如&#xff0c;wordpress主题使用的是simple-life主题&#xff0c;服务器IP为192.168.68.89,在wordpress主题文件中有个页脚文件footer.php&#xff0c;这是一个包含网站页脚代码的文件。 footer.php 路径如下&#xff1a; /www/wwwroot/192.168.68…...

python面向对象编程练习

学生成绩管理系统 定义一个Student类&#xff0c;包括属性&#xff08;姓名、成绩&#xff09;和方法&#xff08;设置成绩、获取成绩、计算平均成绩&#xff09;。 实例化多个学生对象并调用方法。 功能说明&#xff1a; Student 类&#xff1a; init(self, name)&#xff1a;…...

OpenCV_Code_LOG

孔洞填充 void fillHole(const Mat srcBw, Mat &dstBw) {Size m_Size srcBw.size();Mat TempMat::zeros(m_Size.height2,m_Size.width2,srcBw.type());//延展图像srcBw.copyTo(Temp(Range(1, m_Size.height 1), Range(1, m_Size.width 1)));cv::floodFill(Temp, Point(…...

力扣第 74 题是 搜索二维矩阵

题目描述 给定一个 m x n 的矩阵 matrix 和一个目标值 target&#xff0c;请你编写一个函数来判断目标值 target 是否在矩阵中。 每行的元素按升序排列。每列的元素按升序排列。 示例 1 输入&#xff1a; matrix [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14…...

[极客大挑战 2019]BabySQL--详细解析

信息搜集 进入界面&#xff1a; 输入用户名为admin&#xff0c;密码随便输一个&#xff1a; 发现是GET传参&#xff0c;有username和password两个传参点。 我们测试一下password点位能不能注入&#xff1a; 单引号闭合报错&#xff0c;根据报错信息&#xff0c;我们可以判断…...

实现Linux平台自定义协议族

一 简介 我们常常在Linux系统中编写socket接收TCP/UDP协议数据&#xff0c;大家有没有想过它怎么实现的&#xff0c;如果我们要实现socket接收自定义的协议数据又该怎么做呢&#xff1f;带着这个疑问&#xff0c;我们一起往下看吧~~ 二 Linux内核函数简介 在Linux系统中要想…...

RL78/G15 Fast Prototyping Board Arduino IDE 平台开发过程

这是一篇基于RL78/G15 Fast Prototyping Board的Arduino IDE开发记录 RL78/G15 Fast Prototyping Board硬件简介&#xff08;背景&#xff09;基础测试&#xff08;方法说明/操作说明&#xff09;开发环境搭建&#xff08;方法说明/操作说明代码结果&#xff09;Arduino IDE RL…...

YOLOv11 NCNN安卓部署

YOLOv11 NCNN安卓部署 前言 yolov11 NCNN安卓部署 目前的帧率可以稳定在20帧左右&#xff0c;下面是这个项目的github地址&#xff1a;https://github.com/gaoxumustwin/ncnn-android-yolov11 上面的检测精度很低时因为这个模型只训练了5个epoch&#xff0c;使用3090训练一个…...

对载入的3dtiles进行旋转、平移和缩放变换。

使用 params: {tx: 129.75845, //模型中心X轴坐标&#xff08;经度&#xff0c;单位&#xff1a;十进制度&#xff09;//小左ty: 46.6839, //模型中心Y轴坐标&#xff08;纬度&#xff0c;单位&#xff1a;十进制度&#xff09;//小下tz: 28, //模型中心Z轴坐标&#xff08;高…...

Rust个人认为将抢占C和C++市场,逐渐成为主流的开发语言

本人使用C开发8年、C#开发15年、中间使用JAVA开发过项目、后期在学习过程中发现了Rust语言说它是最安全的语言&#xff0c;能够解决C、C的痛点、于是抽出一部分时间网上买书&#xff0c;看网上资料进行学习&#xff0c;这一学习起来发现和其它语言比较起来&#xff0c;在编码的…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...