LeetCode 面试经典 150_回溯_组合（99_77_C++_中等）

LeetCode 面试经典 150_回溯_组合（99_77_C++_中等）

• • 题目描述：
  • 输入输出样例：
  • 题解：
  • • 解题思路：
    • • 思路一（回溯）：
    • 代码实现
    • • 代码实现（思路一（回溯））：

题目描述：

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

题解：

解题思路：

思路一（回溯）：

1、组合问题可以想到回溯。
通过 示例1 中我们发现（仅看前一个位置时）：
1 的组合有 [1,2],[1,3],[1,4]
2 的组合有 [2,3],[2,4]
3 的组合有 [3,4]
总结出一个规律，若 n 为前一个位置，后一个位置必定为 [n+1,n+2,…]

递归出口：组合个数 path.size()==k
递归体：组合问题需控制开始位置(start),防止重复(也就是总结出的规律)，进入函数之前path.push_back(i);退出函数之后path.pop_back();

2、复杂度分析：
① 时间复杂度：O(C(n,k)⋅k)，从n个元素中选择k个元素的组合数。
② 空间复杂度：O(C(n,k)⋅k)，递归调用栈的空间O(k)（path）

代码实现

代码实现（思路一（回溯））：

classSolution{private:vector<vector<int>>ans;// 用于存储所有的组合结果vector<int>path;// 当前组合的路径// 回溯函数，生成从1到n中选择k个数字的组合voidbacktracking(intn,intk,intstart){// 如果当前组合的大小等于k，说明已找到一个组合if(path.size()==k){ans.push_back(path);// 将当前组合存入结果集return;// 返回，继续寻找其他组合}// 从start到n进行迭代，尝试添加数字到当前组合中for(inti=start;i<=n;i++){path.push_back(i);// 将当前数字添加到组合backtracking(n,k,i+1);// 递归调用，继续选择下一个数字path.pop_back();// 撤销选择，回溯}}public:// 主函数，初始化回溯过程并返回结果vector<vector<int>>combine(intn,intk){backtracking(n,k,1);// 从1开始进行组合生成returnans;// 返回所有组合结果}};

LeetCode 面试经典 150_回溯_组合（99_77)原题链接
欢迎大家和我沟通交流(✿◠‿◠)