LeetCode刷题--- 组合

个人主页：元清加油_【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. 所有元素分别作为?位元素进?处理；
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<int>> ret;
vector<int> 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<int>> ret;
    vector<int> 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<int>> combine(int n, int k) 
    {
        N = n;
        K = k;

        dfs(1);

        return ret;
    }
};