力扣第 77 题 组合
题目描述
给定两个整数 n
和 k
,返回范围 [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. 回溯法
回溯法是解决组合问题的经典方法,通过递归构建所有可能的组合。
算法步骤:
- 定义一个函数
backtrack(start, path)
,其中start
表示搜索的起点,path
是当前构建的组合。 - 如果当前组合
path
的长度等于k
,将其加入结果集中。 - 遍历从
start
到n
的所有数字:- 将当前数字加入组合。
- 递归构建下一个数字的组合。
- 回溯,移除当前数字。
回溯法的时间复杂度是 O(C(n, k)),其中 C ( n , k ) = n ! k ! ( n − k ) ! C(n, k) = \frac{n!}{k!(n-k)!} C(n,k)=k!(n−k)!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;
}
代码解析
-
动态数组:
- 使用
Array
结构来动态存储组合结果。 initArray
初始化数组,addToArray
动态增加组合。
- 使用
-
回溯函数:
backtrack
函数递归构建所有可能的组合。- 使用
start
控制数字范围,避免重复组合。
-
主函数:
combine
是主函数,调用回溯并返回结果。- 动态分配
returnColumnSizes
以存储每个组合的列数。
-
内存管理:
- 在主函数中释放动态分配的内存,避免内存泄漏。
时间复杂度和空间复杂度
-
时间复杂度:
- 回溯构造所有组合的复杂度是 O(C(n, k)),即 n ! k ! ( n − k ) ! \frac{n!}{k!(n-k)!} k!(n−k)!n!。
-
空间复杂度:
- 临时数组
combination
的空间复杂度为 O(k)。 - 存储结果的空间复杂度为 O ( C ( n , k ) ⋅ k ) O(C(n, k) \cdot k) O(C(n,k)⋅k)。
- 临时数组
相关文章:
力扣第 77 题 组合
题目描述 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按任意顺序返回答案。 示例 示例 1 输入: n 4, k 2输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]示例 2 输入: n 1, k …...

(超详细图文)PLSQL Developer 配置连接远程 Oracle 服务
1、下载配置文件 (超详细图文详情)Navicat 配置连接 Oracle-CSDN博客 将下载的文件解压到单独文件夹,如:D:\App\App_Java\Oracle\instantclient-basic-windows.x64-19.25.0.0.0dbru 2、配置 打开 PLSQL Developer,登…...

元器件选型与参数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集群-多路径(multipathudev)安装 配置虚拟存储 使用StarWind Management Console软件,配置存储 dggrid1: 1g*3 Dggrid2: 1g*3 Dgsystem: 5g*1 系统表空间,临时表空间,UNDO,参数文件…...
每日速记10道java面试题03
其他资料 每日速记10道java面试题01-CSDN博客 每日速记10道java面试题02-CSDN博客 目录 一、你使用过java的反射机制吗?如何应用反射? 二、什么是泛型?泛型的作用是什么? 三、java的泛型擦除是什么? 四、Java 中…...
Vue 3 的双向绑定原理
Vue 3 的双向绑定原理是基于 响应式系统 和 数据劫持 技术来实现的。在 Vue 3 中,双向绑定通常是通过 v-model 指令来完成的,它本质上是数据的双向同步:当数据改变时,视图自动更新,反之,视图的修改也会更新…...

如何使用 Chrome 无痕浏览模式访问网站?
无痕浏览(Incognito Mode)是 Google Chrome 浏览器提供的一种隐私保护功能,它允许用户在一个独立的会话中浏览网页,而不会记录用户的浏览历史、下载历史、表单数据等。这对于希望保护个人隐私或进行临时性匿名浏览的用户来说非常有…...

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

【小白学机器学习36】关于独立概率,联合概率,交叉概率,交叉概率和,总概率等 概念辨析的例子
目录 1 先说结论 2 联合概率 3 边缘概率 4 (行/列)边缘概率的和 总概率1 5 条件概率 5.1 条件概率的除法公式 5.2 条件概率和联合概率区别 1 先说结论 关于独立概率,联合概率,交叉概率,交叉概率和,总概率 类型含义 …...
Spring Boot 项目——分层架构
在创建一个 Spring Boot 项目时,为了提高代码的可维护性、可扩展性和清晰度,通常会按照一定的分层架构进行设计。常见的分层架构包括以下几层: 1. Controller 层(Web 层) 作用:接收用户请求,并…...

wordpress网站首页底部栏显示网站备案信息
一、页脚文件footer.php 例如,wordpress主题使用的是simple-life主题,服务器IP为192.168.68.89,在wordpress主题文件中有个页脚文件footer.php,这是一个包含网站页脚代码的文件。 footer.php 路径如下: /www/wwwroot/192.168.68…...
python面向对象编程练习
学生成绩管理系统 定义一个Student类,包括属性(姓名、成绩)和方法(设置成绩、获取成绩、计算平均成绩)。 实例化多个学生对象并调用方法。 功能说明: Student 类: init(self, name):…...

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,请你编写一个函数来判断目标值 target 是否在矩阵中。 每行的元素按升序排列。每列的元素按升序排列。 示例 1 输入: matrix [[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14…...

[极客大挑战 2019]BabySQL--详细解析
信息搜集 进入界面: 输入用户名为admin,密码随便输一个: 发现是GET传参,有username和password两个传参点。 我们测试一下password点位能不能注入: 单引号闭合报错,根据报错信息,我们可以判断…...

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

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

YOLOv11 NCNN安卓部署
YOLOv11 NCNN安卓部署 前言 yolov11 NCNN安卓部署 目前的帧率可以稳定在20帧左右,下面是这个项目的github地址:https://github.com/gaoxumustwin/ncnn-android-yolov11 上面的检测精度很低时因为这个模型只训练了5个epoch,使用3090训练一个…...
对载入的3dtiles进行旋转、平移和缩放变换。
使用 params: {tx: 129.75845, //模型中心X轴坐标(经度,单位:十进制度)//小左ty: 46.6839, //模型中心Y轴坐标(纬度,单位:十进制度)//小下tz: 28, //模型中心Z轴坐标(高…...
Rust个人认为将抢占C和C++市场,逐渐成为主流的开发语言
本人使用C开发8年、C#开发15年、中间使用JAVA开发过项目、后期在学习过程中发现了Rust语言说它是最安全的语言,能够解决C、C的痛点、于是抽出一部分时间网上买书,看网上资料进行学习,这一学习起来发现和其它语言比较起来,在编码的…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...