C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题)_回溯算法是dfs吗

1.DFS和回溯算法区别

DFS是一个劲的往某一个方向搜索，而回溯算法建立在DFS基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与DFS的区别就是有无状态重置

2.何时使用回溯算法

当问题需要"回头"，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

3.怎么样写回溯算法(从上而下)

• ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
• ②根据题意，确立结束条件
• ③找准选择列表(与函数参数相关),与第一步紧密关联※
• ④判断是否需要剪枝
• ⑤作出选择，递归调用，进入下一层
• ⑥撤销选择

4.回溯问题的类型

这里先给出，我总结的回溯问题类型，并给出相应的leetcode题目(一直更新)，然后再说如何去编写。特别关注搜索类型的，搜索类的搞懂，你就真的搞懂回溯算法了,但是前面两类是基础，帮助你培养思维

注意：子集、组合与排列是不同性质的概念。子集、组合是无关顺序的，而排列是和元素顺序有关的，如[1，2]和[2，1]是同一个组合(子集)，但[1,2]和[2,1]是两种不一样的排列！！！！因此被分为两类问题

5.子集、组合类问题

A、子集–问题描述：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解题步骤

①递归树

观察上图可得，选择列表里的数，都是选择路径(红色框)后面的数，比如[1]这条路径，他后面的选择列表只有"2、3"，[2]这条路径后面只有"3"这个选择，那么这个时候，就应该使用一个参数start，来标识当前的选择列表的起始位置。也就是标识每一层的状态，因此被形象的称为"状态变量",最终函数签名如下

**nums为题目中的给的数组
**path为路径结果，要把每一条path加入结果集
void backtrack(vector<int>nums,vector<int>&path,int start)
1
2
3

②找结束条件

此题非常特殊，所有路径都应该加入结果集，所以不存在结束条件。或者说当start参数越过数组边界的时候，程序就自己跳过下一层递归了，因此不需要手写结束条件,直接加入结果集

**res为结果集，是全局变量vector<vector<int>>res,到时候要返回的
res.push_back(path);//把每一条路径加入结果集
1
2

③找选择列表

在①中已经提到过了，子集问题的选择列表，是上一条选择路径之后的数(start标识),即

for(int i=start;i<nums.size();i++)
1

④判断是否需要剪枝

从递归树中看到，路径没有重复的，也没有不符合条件的，所以不需要剪枝

⑤做出选择(即for循环里面的)

void backtrack(vector<int>nums,vector<int>&path,int start)
{
    for(int i=start;i<nums.size();i++)
    {
        path.push_back(nums[i]);//做出选择
        backtrack(nums,path,i+1);//递归进入下一层，注意i+1，标识下一个选择列表的开始位置，最重要的一步
    }
}
1
2
3
4
5
6
7
8

⑥撤销选择

整体的backtrack函数如下

void backtrack(vector<int>nums,vector<int>&path,int start)
{
    res.push_back(path);
    for(int i=start;i<nums.size();i++)
    {
        path.push_back(nums[i]);//做出选择
        backtrack(nums,path,i+1);//递归进入下一层，注意i+1，标识下一个选择列表的开始位置，最重要的一步
        path.pop_back();//撤销选择
    }
}
1
2
3
4
5
6
7
8
9
10

---

B、子集 II(剪枝思想)–问题描述:

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

解题步骤

①递归树

可以发现，树中出现了大量重复的集合，②和③和第一个问题一样，不再赘述，我们直接看第四步

**nums为题目中的给的数组
**path为路径结果，要把每一条path加入结果集
void backtrack(vector<int>nums,vector<int>&path,int start)
1
2
3

④判断是否需要剪枝

显然我们需要去除重复的集合，即需要剪枝，把递归树上的某些分支剪掉。那么应去除哪些分支呢？又该如何编码呢？

观察上图不难发现，应该去除当前选择列表中，与上一个数重复的那个数，引出的分支，如“2，2”这个选择列表，第二个“2”是最后重复的，应该去除这个“2”引出的分支。注意：应该先对数组进行排序！！！让相同的元素放在一起，比如[1,5,8,5,1]，排序后[1,1,5,5,8]这样就能检测到当前元素是不是和上一个元素相同

(去除图中红色大框中的分支)

编码呢，刚刚说到是“去除当前选择列表中，与上一个数重复的那个数，引出的分支”，说明当前列表最少有两个数，当i>start时，并且做选择的之前，比较当前数与上一个数(i-1)是不是相同，相同则continue,

void backtrack(vector<int>& nums,vector<int>&path,int start)
    {
        res.push_back(path);
        for(int i=start;i<nums.size();i++)
        {
            if(i>start&&nums[i]==nums[i-1])//剪枝去重
                continue;
        }
    }
1
2
3
4
5
6
7
8
9

⑤做出选择

void backtrack(vector<int>& nums,vector<int>&path,int start)
    {
        res.push_back(path);
        for(int i=start;i<nums.size();i++)
        {
            if(i>start&&nums[i]==nums[i-1])//剪枝去重
                continue;
            temp.push_back(nums[i]);
            backtrack(nums,path,i+1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11

⑥撤销选择

整体的backtrack函数如下

void backtrack(vector<int>& nums,vector<int>&path,int start)
    {
        res.push_back(path);
        for(int i=start;i<nums.size();i++)
        {
            if(i>start&&nums[i]==nums[i-1])//剪枝去重
                continue;
            temp.push_back(nums[i]);
            backtrack(nums,path,i+1);
            temp.pop_back();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

---

C、组合总和–问题描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
输入: candidates = [1,2,3], target = 3,
所求解集为:
[
[1,1,1],
[1,2],
[3]
]

解题步骤

①递归树

(绿色箭头上面的是路径，红色框[]则为结果，黄色框为选择列表)
从上图看出，组合问题和子集问题一样，1,2和2,1是同一个组合，因此需要引入start参数标识，每个状态中选择列表的起始位置。另外，每个状态还需要一个sum变量，来记录当前路径的和，函数签名如下

void backtrack(vector<int>& nums,vector<int>&temp,int start,int sum,int target)
1

②找结束条件

由题意可得，当路径总和等于target时候，就应该把路径加入结果集，并return

 if(target==sum)
        {
            res.push_back(temp);
            return;
        }
1
2
3
4
5

③找选择列表

 for(int i=start;i<nums.size();i++)
1

④判断是否需要剪枝

从①中的递归树中发现，当前状态的sum大于target的时候就应该剪枝，不用再递归下去了

   for(int i=start;i<nums.size();i++)
        {
            if(sum>target)//剪枝
                continue;
        }
1
2
3
4
5

⑤做出选择

题中说数可以无限次被选择，那么i就不用+1。即下一层的选择列表，从自身开始。并且要更新当前状态的sum

   for(int i=start;i<nums.size();i++)
        {
            if(sum>target)
                continue;
            temp.push_back(nums[i]);
            backtrack(nums,temp,i,sum+nums[i],target);//i不用+1(重复利用)，并更新当前状态的sum
        }
1
2
3
4
5
6
7

⑤撤销选择

整体的backtrack函数如下

   for(int i=start;i<nums.size();i++)
        {
            if(sum>target)
                continue;
            temp.push_back(nums[i]);
            backtrack(nums,temp,i,sum+nums[i],target);//更新i和当前状态的sum
            temp.pop_back();
        }
1
2
3
4
5
6
7
8

总结：子集、组合类问题，关键是用一个start参数来控制选择列表！！若有重复元素，应该先排序后去重！最后回溯六步走：

• ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
• ②根据题意，确立结束条件
• ③找准选择列表(与函数参数相关),与第一步紧密关联※
• ④判断是否需要剪枝
• ⑤作出选择，递归调用，进入下一层
• ⑥撤销选择

下一节，将讲解排列类的回溯问题（点击）