力扣第 77 题 组合

news/2024/12/1 8:02:21/

题目描述

给定两个整数 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)

http://www.ppmy.cn/news/1551427.html

相关文章

3.29【机器学习】第五章作业实现

import numpy as np def RBF(x, center_i, beta_i):dist np.sum(pow((x - center_i),2))rho np.exp(-beta_i*dist)return rho# 输出为1 class RBF_network:def __init__(self):self.hidden_num 0self.y 0def createNN(self, input_num, hidden_num, learning_rate, center…

计算机网络八股整理(四)

目录 八股整理&#xff08;四&#xff09;应用层1&#xff1a;怎么解决tcp粘包&#xff1f;2:tcp的拥塞控制介绍一下&#xff1f; 网络场景1&#xff1a;描述一下打开百度首页后发生的网络过程&#xff1f;2&#xff1a;网页非常慢转圈圈的时候需要从哪些方面考虑问题&#xff…

Hive 数据模型 与 Hive SerDe(序列化与反序列化)

Hive 数据模型 Hive 的数据模型是基于 Hadoop 的分布式文件系统&#xff08;HDFS&#xff09;上的数据存储模型&#xff0c;提供了类似于关系数据库的结构&#xff08;如表、分区和桶&#xff09;&#xff0c;但与传统的关系型数据库不同&#xff0c;Hive 更侧重于海量数据的查…

实时数据开发|Flink如何实现不同数据源输入--DataSource模块

DataStream 编程模型 Flink定义DataStream API让用户灵活且高效的编写流式应用。主要分为3部分&#xff1a;DataSource模块&#xff0c;Transformation模块以及DataSink模块。 DataSource模块&#xff0c;主要定义了数据接入功能&#xff0c;将外部数据接入至flink&#xff0…

NCL数据分析与处理

原文&#xff1a;NCL数据分析与处理https://mp.weixin.qq.com/s/0a9_gllN43WfuZgNHKiyDw?token1542274306&langzh_CNNCL用于科学数据计算和可视化的免费软件。它有着非常强大的文件输入和输出功能&#xff0c;可读写netCDF-3、netCDF-4 classic、HDF4、binary、ASCII数据&…

《向量数据库指南》——MoE应用:解锁深度学习新境界的钥匙

在深度学习的广阔天地里,混合专家(MoE)模型如同一把锐利的钥匙,正逐步解锁着各种复杂应用场景的新境界。作为大禹智库的向量数据库高级研究员,同时也是《向量数据库指南》的作者,我深感MoE模型在推动AI技术向前发展中所扮演的重要角色。今天,我将带大家深入探讨MoE模型在…

flutter 多语言 国际化 flutter Intl的使用方法

一使用 flutter Intl Android studio需要添加插件 flutter Intl 路径 File>>Settings>>Plugins>>Marketplace>>flutter Intl>>Install 安装插件重新启动Android studio Android studio 创建一个flutter测试的新项目 在项目文件中配置 ** 添加…

IIS管理器、Sql Server、windows操作系统,nginx

在windows操作系统下&#xff08;win 10&#xff09;&#xff0c;安装完成之后&#xff0c;界面是这样的 IIS管理器分左中右三个大块&#xff0c;左边为服务器目录&#xff0c;中间为功能图标&#xff0c;右边为操作选项&#xff08;左边、中间选择不同功能是会随之显示相关操…