【回溯+剪枝】组合问题！

77. 组合

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 <= 20
• 1 <= k <= n

解题思路：回溯

​ 这道题直接用暴力的话会发现是超时，但是时间复杂度其实是非常高的，我们需要套 k 层 for 循环！所以这种组合的问题就很适合用回溯来解决，特别是当其是组合！

​ 把组合问题抽象为如下树形结构：

​ 接下来就是回溯三部曲：

1. 函数头设计：
   • 因为我们最后要返回一个 vector<vector<int>> ，那么期间我们也得有一个 vector<int> 来记录当前符合条件的结果
   • 除此之外，为了防止出现重复的组合，我们需要一个 cur 变量，比如这次是 [1, 2, 3] 中取 1，那么下一层递归中就要从 2 开始取，不然就会出现 11 的情况！所以需要 curindex 来记录下一层递归，搜索的起始位置。
2. 递归函数出口：
   • 通过这道题我们很清楚的知道终止条件就是要判断这个最后结果的位数也就是 k，那么我们只需要判断 v 数组中的长度是否等于 k，等于说明已经满足了，就不需要再向下递归了，则将当前的结果集放到 ret 中，然后返回即可。
3. 函数体内容：

   • 回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出 for 循环用来横向遍历，而递归的过程是纵向遍历。
     

   • 如此我们才遍历完图中的这棵树。for 循环每次从 cur 开始遍历，然后用 path 保存取到的节点。

   • 并且不要忘记在途中递归向下取下一个数字的时候，返回之后，我们还需要继续一个回溯，也就是将 path 中刚才递归下去的那层的那个 i 去掉，这是为了防止我们取不到下下个数字，比如说 [1, 2, 3] ，我们现在取了 1，并且先继续插入到 path 中，然后我们递归到下一层取了 [1, 2]，此时 2 也会被 push 到 path 中，那么返回回来的时候如果不将 2 pop掉的话，path 就还是 k = 2，那么递归下一层的时候就直接返回了，就取不到 [1, 3] 了！

class Solution {
    vector<vector<int>> ret; // 存放结果集
    vector<int> path;        // 存放当前路径中的元素
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ret;
    }

    void dfs(int n, int k, int cur)
    {
        // 递归函数出口
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }

        for(int i = cur; i <= n; ++i)
        {
            // 处理当前节点
            path.push_back(i);

            // 递归处理当前节点后面的路径
            dfs(n, k, i + 1);

            // 回溯处理
            path.pop_back();
        }
    }
};

剪枝优化

​ 我们说过，回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。在遍历的过程中有如下代码：

for(int i = cur; i <= n; ++i)
{
    path.push_back(i);
    dfs(n, k, i + 1);
    path.pop_back();
}

​ 这个遍历的范围是可以剪枝优化的，怎么优化呢？

​ 来举一个例子，n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。 在第二层 for 循环，从元素 3 开始的遍历都没有意义了。

​ 这么说有点抽象，如图所示：

​ 因为我们要的 k 是 4，但是从 2 开始的话，就算加上 3 和 4，最多就是 3 个数，不可能到达 k = 4 的个数，所以就是无效遍历！所以，可以剪枝的地方就在递归中每一层的 for 循环所选择的起始位置。

​ 也就是说，如果 for 循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

​ 注意代码中 i，就是 for 循环里选择的起始位置。

for(int i = cur; i <= n; ++i)

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size()
2. 还所需的元素个数为: k - path.size()
3. 因为 列表中剩余元素（n - i + 1）≥ 还所需的元素个数（k - path.size()） 才有意义要遍历下去！
4. 所以最后得到：i ≤ n - (k - path.size()) + 1

​ 所以优化之后的 for 循环是：

for(int i = cur; i <= n-(k-path.size())+1; ++i) // 剪枝优化

​ 优化后整体代码如下：

class Solution {
    vector<vector<int>> ret; // 存放结果集
    vector<int> path;        // 存放当前路径中的元素
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return ret;
    }

    void dfs(int n, int k, int cur)
    {
        // 递归函数出口
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }

        for(int i = cur; i <= n-(k-path.size())+1; ++i) // 剪枝优化
        {
            // 处理当前节点
            path.push_back(i);

            // 递归处理当前节点后面的路径
            dfs(n, k, i + 1);

            // 回溯处理
            path.pop_back();
        }
    }
};