因为在进行背包问题的练习时，发现很多题目需要回溯，但本人作为小白当然是啥也不知道

那么就先来补充一下回溯算法的知识点，再进行练习

理论基础

回溯算法本质上是一种递归函数，是纯暴力搜索方法，

适合组合问题、排列问题、切割问题、子集问题，棋盘问题

常见题目如：回文子串，N皇后，解数读

回溯法可以抽象为一个树形结构

对于每个结点处理的集合大小通常用for循环进行遍历

对于树的深度就是递归的深度，用递归处理

回溯算法模板！

void backtracking (参数){

        if(终止条件){

                在叶子结点收集结果;

                return;

        }

        for(集合元素){//遍历结点内元素

                处理结点;

                backtracking;//递归函数

                回溯操作;//撤销处理结点的情况

        }

        return;

}

        

---

题目一：组合

问题描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

解题步骤

在n和k都较小的情况下，我们利用嵌套for循环就能解决

但如果n，k都比较大，那么我们就需要嵌套k个循环，

这是非常不合理的，代码编写也没有那么容易

那么我们就需要使用回溯算法，利用递归解决多层循环嵌套

具体操作就按照回溯三部曲来进行（其实和递归三部曲是一样的）

1.确定递归函数的返回值以及参数

套用模板，返回值一般都是void，特事特办才需要修改，本题不需要

我们要处理多个数字，组合得到目标个数的结果

那么数字范围要作为参数，目标个数也需要，

同时，组合是没有次序区别的，

所以为了避免重复，我们需要加入一个不断递增量改动开始位置startindex

void backtracking(int n, int k, int startIndex)

为了方便得到结果与存放过程量

可以定义两个全局变量

vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果

2.明确回溯终止条件

根据我们的推理，最后我们希望得到的是长度为k的数字组合

每一层递归将会往组合中加入一个数字，需要k个就要递归k次

每次的路径决定数字，逐渐形成path,成形后把整个path加入最后要返回的大集合result里

if(path.size()==k){

        result.push_back(path);

        return;

} 

3.单层搜索过程

第一层，我们需要从1开始，遍历到1就加入path，再进入递归函数选择出下一个数字

那么下一个数字只能从2开始选择，选择完毕需要再加入这个结点，以供下一个数字开头时使用

那么外层就是很简单从1开始遍历到n给每个数字一个做开头的机会（只是这样不会弄错弄乱，避免出现少考虑的情况，实际上没有顺序意义）

for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.push_back(i); // 处理节点
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

那么这个和回溯模板基本一样的经典题关键代码已经完成！

最后在写一下主函数，完善一下逻辑即可

vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }

 完整代码如下！

code

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(int n,int k,int startindex){if(path.size()==k){result.push_back(path);return;}for(int i=startindex;i<=n;i++){path.push_back(i);backtracking(n,k,i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return result;}
};

ok想必大家发现这个程序其实可以改进一下，

例如n=4，k=2时，当这个n遍历到4时其实就咩有必要了，没有数字可供他选择组合

所以在这个遍历终点处，我们可以进行一下剪枝优化

目前组合长度为：path.size(),这个值是从0开始的

还需要数字个数为：k - path.size()

列表剩余数字个数为：n - i, i 是从1开始的

应该让 剩余大于等于需要：n - i >= k - path.size() + 1（+1是为了统一两边步调）

变化一下不等式：i <= n - (k - path.size() )- 1

那么这个循环就变为了

for (int i = startindex; i <= n - (k - path.size()) + 1; i++){

 全部代码只需要改动这一行就可以避免很多不必要的操作，减少浪费

---

题目二：组合总和③

问题描述

216. 组合总和 III - 力扣（LeetCode）

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

解题步骤

这一题和上一题有很多相似之处，

区别在于，固定数字范围[1,9],给出目标和 n

那么我们可以用同样的思路现在1~9中找出包含k个数的所有组合

再通过计算，求和与目标和进行比较，如果相等则加入到最后的result数组中

同时呢，由于我们只需要在9个数字中取舍，优化的效果就没那么大了，可以不用

所以动手操作下来，在终止条件中加上sum==n，并在这之前执行sum计算即可

int sum=accumulate(path.begin(),path.end(),0);

        if(path.size()==k && sum==n){

完整代码如下！ 

code

class Solution {
public:vector<int> path;vector<vector<int>> result;void backstacking(int k,int n,int startindex){int sum=accumulate(path.begin(),path.end(),0);if(path.size()==k && sum==n){result.push_back(path);return;}for(int i=startindex;i<=9;i++){path.push_back(i);backstacking(k,n,i+1);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backstacking(k,n,1);return result;}
};