leetcode77.组合

leetcode77.组合

组合

题目抽象

我们把组合问题抽象为以下树形结构：

我们将上图的树形结构称之为决策树，从决策树中我们可以看出，n决定决策树的宽度即循环次数，而k决定决策树的深度即递归次数

我们挑选出某一具体路径来进行分析。我们在得到[1,2]后递归返回，想要再得到[1,3],就需要把2

“还回去”，因此，这便是一道经典的回溯问题

回溯三部曲

• 确定递归函数的函数头

首先我们要定义两个全局变量

• vector<vector<int>> ret：存放最终返回值
• vector<int> path：存放某一符合要求的结果

也可以将这两个全局变量当作参数传递给递归函数

void dfs(int n, int k, int start)

start用来确定下一层递归的开始位置，调用下一层递归函数时传入start+1，可以避免取到重复元素

• 单层遍历的过程

在for循环中，i从start位置开始遍历，path存放取到的值，调用下一层递归，递归结束后回溯

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

• 确定递归函数终止条件

当path.size() == k时递归终止，将path加入ret中后返回

if(path.size() == k)
{
    ret.push_back(path);
    return;
}

完整代码

vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
    dfs(n,k,1);
    return ret;
}
void dfs(int n,int k,int start)
{
    if(path.size() == k)
    {
        ret.push_back(path);
        return;
    }
    for(int i=start;i<=n-k+path.size()+1;i++)
    {
        path.push_back(i);
        dfs(n,k,i+1);
        path.pop_back();
    }
}