(回溯) LeetCode 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 <= 201 <= k <= n
二. 解题思路
本题意思是给定一个数字n 以及 k ，在1到n 中找到组合大小位k 的所有可能输出，可能有些同学想到了使用for循环去遍历，但是单传使用for循环去嵌套遍历有两个缺点：（1）首先你不知道k的大小，不能够确定各for循环的嵌套次数；（2）其次，即便你知道了k的值，使用for循环去嵌套遍历，那如果题目中给你100个数，k的值为50，让你在100个数中找出所有组合大小为50的组合数，你难道还想用50层for循环去遍历吗？？？当然不行，那么这里我们就选择回溯：
回溯其实也是for循环的一种体现，通过递归的思想实现对组合数的判断，也是一种暴力的做法，不过比for循环好。
话不多说！！！上代码！！
三. 代码
class Solution {
public:vector<vector<int>> res;vector<int> path;void back(int n, int k, int startindex){if(path.size() == k){ //如果达到了组合数的要求就退出res.push_back(path);return;}for(int i = startindex; i <= n; i++){path.push_back(i);back(n, k, i + 1);path.pop_back(); // 回溯：到上一个阶段}}vector<vector<int>> combine(int n, int k) {back(n, k, 1);return res;}
};四. 总结
对于回溯算法，本身比较抽象，也晦涩难懂，需要多加练习和理解，掌握原理即可，加油！！
时间复杂度：O(N∗K)；
空间复杂度：O(N∗K)。