算法题每日一练---第85天：组合

一、问题描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

题目链接：组合

二、题目要求

样例

输入： n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

考察

1.回溯算法
2.建议用时15~25min

三、问题分析

正式讲解之前，我们先思考一下：只最简单的编程，不用任何算法如何解决？

以样例为例，1 2 3 4 选出集合个数为2的子集，用两重for循环不就解决了。

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

那假如n=10,k=3，三重循环就行。n=100,k=50呢？

不可能要写50重for循环吧，骡子也撑不住这样写代码啊。

所以，我们的主角，回溯大法就要来了，此招式分为四式：

第一式：函数初始

我们要初始化一个函数来承载回溯，函数里面的参数如何确定呢？

首先，如上图所示这一题从1开始，到n结束，要求集合里面k个数字。

    vector<int>t;
    vector<vector<int>>v;//初始化数组
void DFS(int cur,int n,int k)

第二式：终止条件

什么时候结束继续向下开始搜索的条件呢？

题目要求k个数字，所以只要

if(t.size()==k)//符合要求
{
     v.push_back(t);
     return;
}

第三式：剪枝优化

但对于执行到一半，我们就知道不可能出现结果的部分可以优化，这部分称为剪枝，就是去掉多余的枝条不影响结果。

假设1 2 3 4 5里面选择3个数字，那么遍历到4为开头的时候，就发现无论如何遍历都不能满足3个数字，这个时候不需要向下遍历。

if (t.size()+(n-cur + 1) < k) 
            return;

第四式：递归处理

for(int i=cur;i<=n;i++)
{
     t.push_back(i);//选择当前数字
     DFS(i+1,n,k);
     t.pop_back();//回退
} 

cur代表的是当前的数字，我们要向下加入数字到集合之中，DFS下面的一行代表什么？

假如现在t里面存储了1 2，如果我们不把2弹出，那么3如何加入进来。

过程应该是：

加入后：1
加入后：[1 2]
回溯后：1
加入后：[1 3]
回溯后：1
加入后：[1 4]
回溯后：1
回溯后：[]
加入后：2
加入后：[2 3]
回溯后：2
加入后：[2 4]
回溯后：2
回溯后：[]
加入后：3
加入后：[3 4]

模板：

void DFS(变量)//函数初始
{
    if(条件1||条件2...)//终止条件
    {
         v.push_back(t);
         return;
    }
    if (条件1||条件2...)//剪枝
         return;
    for(int i=cur;i<=n;i++)//递归处理
    {
        //选择当前数字
        DFS(向下遍历);
        //回退
    } 
}

冲冲冲！

四、编码实现

class Solution {
public:
    vector<int>t;
    vector<vector<int>>v;//初始化数组
    void DFS(int cur,int n,int k)//函数初始
    {
        if(t.size()==k)//终止条件
        {
            v.push_back(t);
            return;
        }
        if (t.size()+(n-cur + 1) < k)//剪枝
            return;
        for(int i=cur;i<=n;i++)//递归处理
        {
            t.push_back(i);//选择当前数字
            DFS(i+1,n,k);
            t.pop_back();//不选当前数字
        } 
    }
    vector<vector<int>> combine(int n, int k) {
        DFS(1,n,k);
        return v;
    }
};

五、测试结果

图2优化后的结果。