77. 组合

简介: 回溯法是一种通过递归搜索解决问题的算法,适用于组合、切割、子集、排列和棋盘等问题。以“77. 组合”为例,给定整数n和k,需找出[1, n]中所有可能的k个数的组合。此问题可抽象为树形结构,n为树宽,k为树深。通过递归与回溯,每次从集合中选取元素并调整范围,当路径长度等于k时收集结果。题解中使用`backtracking`函数实现递归,利用`path`记录当前组合,最终返回所有符合条件的结果。

理论基础:

什么是回溯法?

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。

回溯法解决的问题

回溯法,一般可以解决如下几种问题:

组合问题:N个数里面按一定规则找出k个数的集合

切割问题:一个字符串按一定规则有几种切割方式

子集问题:一个N个数的集合里有多少符合条件的子集

排列问题:N个数按一定规则全排列,有几种排列方式

棋盘问题:N皇后,解数独等等

如何理解回溯法?

回溯法解决的问题都可以抽象为树形结构,是的,我指的是所有回溯法的问题都可以抽象为树形结构!

因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。

递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

 题目:

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

思考历程与知识点:  

每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。

图中可以发现n相当于树的宽度,k相当于树的深度。

图中每次搜索到了叶子节点,我们就找到了一个结果。

相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。

题解:

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯,撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};


相关文章
|
JavaScript 前端开发
在VSCode中 使用 ESLint + Prettier检查代码规范及自动格式化前端Vue代码
般的代码格式化工作,ESLint完全可以胜任,为什么要用Prettier代替ESLint的代码格式化功能?简而言之,Prettier的代码格式化功能比ESLint更强大,配置更简单,通过配置,ESLint可以使用Prettier的代码规则进行校验,如果不配置好,会出现冲突,导致二者不能配合使用。 下面详细介绍如何配置ESLint+Prettier在VSCode中开发Vue代码:
2395 29
在VSCode中 使用 ESLint + Prettier检查代码规范及自动格式化前端Vue代码
|
7月前
|
机器学习/深度学习 数据采集 人工智能
大模型应用:小样本学习的高性价比:轻量算法做基底,大模型做精修.84
本文提出“轻量算法+大模型”协同的小样本分类新范式:轻量模型(如逻辑回归)快速初筛高置信样本,大模型仅精修低置信疑难样本,实现成本降75%、准确率不损、可解释性增强,破解小样本落地难题。
770 8
|
6月前
|
人工智能 监控 安全
告别传统Prompt写法!聚AI提示词工程新范式
本章系统讲解Python提示词工程实战,涵盖专业环境搭建、API调用与结构化响应、企业级模板引擎及多步骤对话管理,并延伸至Prompt迭代优化、外部工具集成与性能监控,助力构建工业级AI应用系统。(239字)
360 1
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
1139 1
|
机器学习/深度学习 人工智能 搜索推荐
DeepSeek-V2.5-1210 在线开放使用!支持联网搜索,在各大领域的表现得到全面提升
DeepSeek-V2.5-1210 是 DeepSeek V2.5 系列的最终版微调模型,支持联网搜索功能,具备在数学、编程、写作和角色扮演等领域的能力提升。本文将详细介绍该模型的功能、技术原理及应用场景。
10901 19
DeepSeek-V2.5-1210 在线开放使用!支持联网搜索,在各大领域的表现得到全面提升
|
应用服务中间件
dist文件夹、src文件夹、dest文件夹作用
dist文件夹、src文件夹、dest文件夹作用
1361 0
|
Java
java基础 - 个人笔记
java基础 - 个人笔记
952 2
|
Ubuntu Linux 测试技术
探索Linux中的`dbus-send`命令
`dbus-send`是Linux中用于进程间通信的D-Bus系统的命令行工具,允许应用程序通过消息总线相互交互。要安装它,可以使用包管理器(如`apt-get`或`dnf`)。基本语法包括指定总线类型、目标服务、消息类型、对象路径、接口及方法等。示例用法包括使用`dbus-send`来锁定屏幕(通过调用`org.gnome.ScreenSaver.Lock`)和设置音量(通过与PulseAudio服务交互)。在使用时,需了解目标服务的接口和方法,并确保具备相应权限。
1409 10
|
消息中间件 存储 Java
RocketMQ技术详解:从基础知识到内部设计原理
RocketMQ技术详解:从基础知识到内部设计原理
745 2
|
Python
还不会免费将PDF转为Word?你可以试试这3种工具!
还不会免费将PDF转为Word?你可以试试这3种工具!
972 0