【Leetcode每日一题】综合练习 - 组合（难度⭐⭐）（78）

devtools/2024/10/15 5:47:58/

1. 题目解析

题目链接：77. 组合

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

题目要求我们从 1 到 n 的整数集合中选择 k 个数的所有组合，且组合中的元素不考虑顺序。这意味着集合 [1, 2] 和 [2, 1] 被视为等价。为了找出所有不重复的组合，我们可以采用深度优先搜索（DFS）的策略，并在搜索过程中遵循一定的规则来避免产生重复的组合。

DFS函数设计

函数名：void dfs(vector<vector<int>>& ans, vector<int>& curr, int step, int n, int k)

ans：用于存储所有找到的组合的二维数组。
curr：用于存储当前正在构建的组合的一维数组。
step：当前处理的位置，即 curr 数组中下一个要填充的位置。
n：可选元素的上限。
k：需要选择的元素个数。

具体实现步骤

初始化：
- 定义一个二维数组 ans 用于存储所有找到的组合。
- 定义一个一维数组 curr 用于存储当前正在构建的组合。
递归逻辑：
- 结束条件：当 step 达到 k 时，表示当前组合已经包含了 k 个元素，将其添加到 ans 中，并返回。
- 剪枝：如果当前位置 step 加上剩余可选元素个数（n - step + 1）小于 k，表示从当前位置开始无法构造出满足要求的组合，直接返回。
- 递归调用：从 step 开始遍历到 n，对于每个遍历到的元素 i，执行以下操作：
  - 将 i 添加到 curr 数组的 step 位置。
  - 递归调用 dfs 函数，传入更新后的 curr 数组、step + 1（表示处理下一个位置）、n 和 k。
  - 回溯：在递归返回后，需要将 curr 数组中 step 位置的元素移除，以便尝试其他可能的元素。

算法逻辑解释

通过遍历 1 到 n 的每个元素作为组合的首位元素，我们可以确保每个组合的首位元素都是唯一的。
在递归过程中，我们始终保证当前位置 step 的元素不小于前一个位置的元素，从而避免了产生重复的组合（如 [1, 2] 和 [2, 1]）。
当组合中元素的个数达到 k 时，我们将其视为一个有效的组合，并存储起来。
通过剪枝操作，我们可以提前终止那些无法构造出满足要求组合的递归分支，从而提高算法的效率。

3.代码编写

class Solution {vector<int> path;vector<vector<int>> ret;int m, o;
public:vector<vector<int>> combine(int n, int k) {o = n, m = k;dfs(1);return ret;}void dfs(int start){if(path.size() == m){ret.push_back(path);return;}for(int i = start; i <= o; i++){path.push_back(i);dfs(i + 1); // 下一层是从我添加的这个数开始的path.pop_back();}}
};