77. 组合 - 力扣（LeetCode）

题目描述

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

题解

暴力算法

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

在上述暴力算法中，题目中k等于多少，我们就要嵌套多少个for循环，显然这样写代码是不合理的，而在回溯算法中，我们用递归代替嵌套的for循环

回溯算法

核心

• for循环的本质是遍历每一层
• 递归的本质是遍历每个深度下的树枝

核心代码：

        //横向遍历
        for(int i=startIndex;i<=n;i++)
        {
            path.emplace_back(i);//处理节点
            backing(n,k,i+1,path,res);//纵向遍历
            path.pop_back();//回溯
        }

在上述代码中，我们用for循环用来横向遍历，递归的过程是纵向遍历。同时用startIndex控制每层遍历的起始位置，每往深层下降一层就用path保存取到的节点i，当满足终止条件return返回到上一层前要进行回溯，撤销处理的结点。

也就是说，backing（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。

那么终止条件是什么呢？很显然，每当我们收集path的过程中path的大小等于k的时候，就说明我们已经收集到了一个满足题意的结果，此时即可终止本次递归，返回上一层，即：

        //递归出口
        if(path.size()==k){
            res.push_back(path);//收集结果
            return;
        }

剪枝优化

在上述遍历过程中，我们是可以对遍历范围进行剪枝优化的。

比如，当n=4，k=4时，那么我们在遍历第一层时，当元素2开始到之后的遍历就没有意义了，因为k=4，也就是path中要有4个元素，但是从元素2开始向后哦遍历取元素时，path的最多个数也就是3个，不满足题意，因此从元素2开始，其后的遍历就没有必要了。

同理在第2层遍历中，从元素3开始，到之后的遍历也没有意义。

整个剪枝过程如下：

那么，如何控制剪枝呢？

• 其一，path.size()表示当前已经取到的元素个数
• 其二，k-path.size()表示我们还需要取的元素个数
• 那么，n-(k-path.size())+1就表示，我们最多在每层遍历时，起始遍历的位置

故优化后for循环为：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

代码

class Solution {
public:
    void backing(int& n,int& k,int startIndex,vector<int>& path,vector<vector<int>>& res)
    {
        //递归出口
        if(path.size()==k){
            res.push_back(path);//收集结果
            return;
        }
        
        //横向遍历，n-(k-path.size())+1为剪枝优化
        for(int i=startIndex;i<=n-(k-path.size())+1;i++)
        {
            path.emplace_back(i);
            backing(n,k,i+1,path,res);//纵向遍历
            path.pop_back();//回溯
        }
    }

    vector<vector<int>> combine(int n, int k) {

        vector<int> path;
        vector<vector<int>> res;
        backing(n,k,1,path,res);
        return res;
    }
};