个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

http://t.csdnimg.cn/yUl2I

【C++】

http://t.csdnimg.cn/6AbpV

数据结构与算法

​​​​​​http://t.csdnimg.cn/hKh2l

前言：这个专栏主要讲述递归递归、搜索与回溯算法，所以下面题目主要也是这些算法做的

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

组合

题目链接：

题目

给定两个整数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，返回范围[1, n]中所有可能的k个数的组合。

你可以按任何顺序返回答案

示例 1：

输入：n = 4, k = 2输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

算法原理思路讲解

题⽬要求我们从 1 到 n 中选择 k 个数的所有组合，其中不考虑顺序。也就是说，[1,2] 和 [2,1] 等价。我们需要找出所有的组合，但不能重复计算相同元素的不同顺序的组合。对于选择组合，我们需要进⾏如下流程：

  1. 所有元素分别作为⾸位元素进⾏处理；
  2. 在之后的位置上同理，选择所有元素分别作为当前位置元素进⾏处理；
  3. 为避免计算重复组合，规定选择之后位置的元素时必须⽐前⼀个元素⼤，这样就不会有重复的组合（[1,2] 和 [2,1] 中 [2,1] 不会出现）。

一、画出决策树

以 n = 4，k = 2 为例子

既然是树形问题上的 深度优先遍历，因此首先画出树形结构。例如输入：n = 4, k = 2，我们可以发现如下递归结构：

  1. 如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 1个数；
  2. 如果组合里有 2 ，那么需要在 [3, 4] 里再找 1 数。注意：这里不能再考虑 1，因为包含 1的组合，在第 1 种情况中已经包含。

依次类推（后面部分省略），以上描述体现的 递归 结构是：在以 nnn 结尾的候选数组里，选出若干个元素。画出递归结构如下图：

决策树就是我们后面设计函数的思路

二、设计代码

（1）全局变量

vector<vector> ret;vector path;int N, K;
  • path（记录路径的组合）
  • ret（存放所有组合可能）
  • N （范围的大小）
  • K （组合的个数）

（2）设计递归函数

void dfs(int pos);
  • 参数：pos（当前需要进⾏处理的位置）
  • 返回值：⽆；
  • 函数作⽤：某个元素作为⾸位元素出现时，查找所有可能的组合。

递归流程如下：

  1. 定义⼀个⼆维数组和⼀维数组。⼆维数组⽤来记录所有组合，⼀维数组⽤来记录当前状态下的组合。
  2. 遍历 1 到 n，以当前数作为组合的⾸位元素进⾏递归
  3. 递归函数的参数为两个数组、当前步骤以及 n 和 k。递归流程如下：
    1. 结束条件：当前组合中已经有 k 个元素，将当前组合存进⼆维数组并返回。
    2. 剪枝：如果当前位置之后的所有元素放⼊组合也不能满⾜组合中存在 k 个元素，直接返回。 从当前位置的下⼀个元素开始遍历到 n，将元素赋值到当前位置，递归下⼀个位置

以上思路讲解完毕，大家可以自己做一下了

代码实现

  • 空间复杂度：O(n+k)=O(n)，即递归使用栈空间的空间代价和临时数组 path的空间代价。

class Solution {public:vector<vector> ret;vector path;int N, K;void dfs(int pos){if (path.size() == K){ret.push_back(path);return ;}for (int i = pos; i <= N; i++){path.push_back(i);dfs(i+1);path.pop_back();}}vector<vector> combine(int n, int k) {N = n;K = k;dfs(1);return ret;}};