Leetcode No.77 组合
一、题目描述
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
二、解题思路
重点概括：
如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法； 回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）； 组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。
回溯算法首先需要画出递归树，不同的树决定了不同的代码实现。下面给出了两种画树的思路。
方法一：根据搜索起点画出二叉树 既然是树形问题上的 深度优先遍历，因此首先画出树形结构。例如输入：n = 4, k = 2，我们可以发现如下递归结构：
如果组合里有 1 ，那么需要在 [2, 3, 4] 里再找 1 个数； 如果组合里有 2 ，那么需要在 [3, 4] 里再找 1数。注意：这里不能再考虑 1，因为包含 1 的组合，在第 1 种情况中已经包含。 依次类推（后面部分省略），以上描述体现的 递归 结构是：在以 n结尾的候选数组里，选出若干个元素。画出递归结构如下图：
说明：
叶子结点的信息体现在从根结点到叶子结点的路径上，因此需要一个表示路径的变量 path，它是一个列表，特别地，path 是一个栈； 每一个结点递归地在做同样的事情，区别在于搜索起点，因此需要一个变量 start ，表示在区间 [begin, n] 里选出若干个数的组合； 可能有一些分支没有必要执行，我们放在优化中介绍。 友情提示：对于这一类问题，画图帮助分析是非常重要的解题方法。
class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
vector<vector<int>> combine(int n, int k) {
dfs(1,n,k);
return ans;
}
void dfs(int cur, int n,int k) {
// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
if (temp.size() + (n - cur + 1) < k) {
return;
}
// 记录合法的答案
if (temp.size() == k) {
ans.push_back(temp);
return;
}
// cur == n + 1 的时候结束递归
if (cur == n + 1) {
return;
}
// 考虑选择当前位置
temp.push_back(cur);
dfs(cur + 1, n, k);
temp.pop_back();
// 考虑不选择当前位置
dfs(cur + 1, n, k);
}
};方法二：按照每一个数选与不选画出二叉树
可以按照每一个数选与不选画出二叉树，二叉树最多 n 层。同样可以剪枝。剪枝的思路请见下图「剪枝条件 ② 的加强」。
画一个表格更容易看出边界条件。
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<int> path;
vector<vector<int>> rs;
dfs(1,n,k,path,rs);
return rs;
}
void dfs(int begin, int n,int k,vector<int> path,vector<vector<int>> &rs) {
if(k==0){
rs.push_back(path);
return;
}
if(begin>n-k+1){
return;
}
dfs(begin+1,n,k,path,rs);
path.push_back(begin);
dfs(begin+1,n,k-1,path,rs);
path.pop_back();
}
};三、复杂度分析
时间复杂度：我们已经得到了一个时间复杂度为 O(
) 的组合枚举，由于每次记录答案的复杂度为 O(k)，故这里的时间复杂度为 O(
*k)
空间复杂度：O(n + k) = O(n)，即递归使用栈空间的空间代价和临时数组temp 的空间代价。