【回溯算法】回溯的组合与排列问题
- 回溯算法理论基础
- 什么是回溯
- 回溯法模板
- 组合问题
- 组合优化
- 组合总和Ⅲ
- 电话号码的字母组合
- 组合总和
- 组合总和2🚩
- 回溯三部曲
- 全排列
- 全排列Ⅱ
回溯算法理论基础
什么是回溯
-
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
-
回溯是递归的副产品，只要有递归就会有回溯。所以以下回溯函数也就是递归函数，指的都是一个函数。
-
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。
回溯法解决的问题
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯法解决的问题都可以抽象为树形结构， 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
回溯法模板
- 回溯函数伪代码如下：
void backtracking(参数) - 回溯函数终止条件
if (终止条件) {存放结果;return; } - 回溯搜索的遍历过程
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果 }
回溯算法模板框架如下：
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
组合问题
力扣原题连接：77. 组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
把组合问题抽象为如下树形结构：
-
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
-
图中可以发现n相当于树的宽度，k相当于树的深度。
-
图中每次搜索到了叶子节点，我们就找到了一个结果。
回溯三部曲
（1）递归函数的返回值以及参数
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合，代码如下：
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果
函数里一定有两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数。然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历，startIndex 就是防止出现重复的组合。
所以需要startIndex来记录下一层递归，搜索的起始位置。
那么整体代码如下：
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex)
（2）回溯函数终止条件
path这个数组的大小如果达到k，则找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径，如图红色部分：
此时用result二维数组，把path保存起来，并终止本层递归。
所以终止条件代码如下：
if (path.size() == k) {result.push_back(path);return;
}
（3）单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程，如下图，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
for 循环每次从 startIndex 开始遍历，然后用 path 保存取到的节点i，代码如下：
// 控制树的横向遍历
for (int i = startIndex; i <= n; i++)
{ path.push_back(i); // 处理节点backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始path.pop_back(); // 回溯，撤销处理的节点
}
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
问题C++完整代码如下：
class Solution {
public:vector< vector<int> > res;vector<int> path;void backtracking(int n, int k, int startIdx){//终止条件if(path.size() == k) //找到一个大小为k的组合{res.push_back(path); //path加入结果数组中 收割结果return;}//单层递归逻辑for(int i = startIdx; i <= n; i++){path.push_back(i); //数据加入组合backtracking(n, k, i+1); //递归path.pop_back(); //回溯}return;}vector< vector<int> > combine(int n, int k) {backtracking(n, k, 1);return res;}
};
以上代码则是回溯算法的一个模板，需熟记
组合优化
回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的，一般在单层搜索的轮数和提前终止条件上做优化。
来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。
- 所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
- 如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
就是for循环里选择的起始位置，🚩优化过程如下：
::
- 已经选择的元素个数：
path.size(); - 所需需要的元素个数为：
k - path.size(); - 列表中剩余元素
（n-i）>= 所需需要的元素个数（k - path.size()） - 在集合n中至多要从该起始位置：
i <= n - (k - path.size()) + 1，开始遍历
为什么有个+1呢？因为包括起始位置，我们要是一个左闭的集合，举个例子更好理解：n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。从2开始搜索都是合理的，可以是组合[2, 3, 4]。
所以优化之后的for循环是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
组合总和Ⅲ
力扣题目链接：216.组合总和Ⅲ
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
思路
相对于组合，无非就是多了一个限制（求和相等），本题是要找到和为n的k个数的组合，而整个集合已经是固定的了[1,…,9]。
选取过程如图：
🚩 模板题：
- 结束条件：path.size() == k，计算sum是否等于targetSum
- 减枝：
for (int i = start; i <= 9 - (k - path.size()) + 1; i++)
对于代码如下：
/**************************算法****************************/
class Solution {
public:vector< vector<int> >res;vector<int>path;int temp_sum;void backtracking(int k, int targetSum, int sum, int startIdx){if(sum > targetSum) // 减枝1 和过大return; //终止条件if(path.size() == k){if(targetSum == sum)res.push_back(path);return;}//单层递归逻辑for(int i = startIdx; i <= 9 - (k - path.size()) + 1; i++) // 减枝2 个数限制{sum += i;path.push_back(i);backtracking(k, targetSum, sum, i+1); //递归//回溯sum -= i;path.pop_back(); }return;}vector< vector<int> > combinationSum3(int k, int n) {backtracking(k,n,0,1);return res;}
};
说明： 从本题起是二刷整理，过程较为简略，主要记录核心思路、模糊错误的点，详细具体过程请参考 【代码随想录-回溯算法】😄
电话号码的字母组合
力扣链接
- 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
- 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
递归返回：path.size == digits.size
为每个数字建立字母映射：
string numMap[10] ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
单层递归逻辑： 处理每个数字，遍历每个数字对应3个字母依次加入路径组合，形成不同的组合
// 处理单个数字逻辑for (int i = start; i < digits.size(); i++){// 处理每个数字的字母组合for (auto ch: numMap[digits[i] - '0']){path.push_back(ch);backtracking(digits, i + 1); // 递归每个数字path.pop_back(); // 回溯}}
完整程序：
class Solution {
public:// 数字 字母映射string numMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> res;string path;void backtracking(const string& digits, int start){// 收集到结果了if (path.size() == digits.size()){res.push_back(path);return;}// 处理单个数字逻辑for (int i = start; i < digits.size(); i++){// 处理每个数字的字母组合for (auto ch: numMap[digits[i] - '0']){path.push_back(ch);backtracking(digits, i + 1); // 递归每个数字path.pop_back(); // 回溯}}return;}vector<string> letterCombinations(string digits) {res.clear();path.clear();if (digits.size() == 0)return res; backtracking(digits, 0);return res;}
};
组合总和
力扣链接
- 无重复元素的数组nums和一个目标整数 target ，找出 nums中可以使数字和为目标数 target 的 所有 不同组合，元素可重复使用
- 输入：nums=[2,3,5], target = 8,
- 输出: [[2,2,2,2],[2,3,3],[3,5]]
套用模板：递归遍历的时候从 🚩自身开始递归，即重复使用本身
backtracking(candidates, target, i);
剪枝优化： 其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
单层递归循环范围：
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < nums.size() && sum + nums[i] <= target; i++)
回溯程序：
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {// 可不加 下面有剪枝 没有剪枝需要这种情况的返回if(sum > target) return;if (sum == target) {result.push_back(path);return;}// 如果 sum + candidates[i] > target 就终止遍历for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);// 回溯sum -= candidates[i];path.pop_back();}
}
组合总和2🚩
- 有重复元素的集合nums和target, 但每个元素只能使用一次
- 输入 nums = [2,5,2,1,2], target = 5,
- 输出:[ [1,2,2], [5] ]
🚩 去重方法不熟悉，该去重方法十分重要，需谨记
- 所谓去重，其实就是使用过的元素不能重复选取
- 所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
- 树层去重的话，需要对数组排序！
回溯三部曲
递归函数参数： 与组合总和套路相同，此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。
void backtracking(vector<int>& nums, int target, int start, vector<bool>& used)
递归终止条件： 同组合总和 判断sum和target大小区别
// 这个条件其实可以省略 因为后面可以减枝
if (sum > target) {return;
}
if (sum == target) {result.push_back(path);return;
}
单层搜索的逻辑
如何判断同一树层上元素（相同的元素）是否使用过了呢❓
如果 nusm[i] == nums[i - 1] 并且 used[i - 1] == false
就说明：前一个树枝，使用了nums[i - 1]，也就是说同一树层使用过nums[i - 1]
抽象，非常抽象 😭 画个图好理解一点
🚩整理：
- 首先，这个数得和前面那个数相同，才有去重这个说法吧，nums[i] == nums[i-1]
- 其次，这个数在同一层上，前面用过一次了，现在取下个同样的数，之前那个就不取，false，那么现在取到的就重复了啊，不能用，抽象😭
- 最后，为了避免 i-1 有意义，i > 1
used[i - 1] == true，说明同一树枝nums[i - 1]使用过used[i - 1] == false，说明同一树层nums[i - 1]使用过
为什么 used[i - 1] == false 就是同一树层❓
同一树层，used[i - 1] == false 才能表示，当前取的 nums[i] 是从 nums[i - 1] 回溯而来的。而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：
整体C++代码如下
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;// 和组合总和的区别，这里是i+1，每个数字在每个组合中只能使用一次backtracking(candidates, target, sum, i + 1, used); // 回溯used[i] = false;sum -= candidates[i];path.pop_back();}
}
注意sum + candidates[i] <= target为剪枝操作，在组合总和有涉及。
全排列
力扣链接
- 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
- 输入: [1,2,3]
- 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
以[1,2,3]为例，抽象成树形结构如下：
回溯三部曲
（1）递归函数参数：
-
首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
-
但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used)
（2）递归终止条件： path.size() == nums.size()
🚩（3）单层搜索的逻辑：
- 排序问题不要需startIdx了，因为排列问题每次都是从头开始搜索
- 而used数组，记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
代码如下：
for (int i = 0; i < nums.size(); i++)
{if (used[i] == true) continue; // path里已经收录的元素，直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;
}
整体C++代码如下：
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used)
{if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); i++){// 排列需要记录元素的使用情况if (used[i] == true)continue;path.push_back(nums[i]);used[i] = true;// 递归backtracking(nums, used);// 回溯path.pop_back();used[i] = false;}return;
}
全排列Ⅱ
力扣链接
- 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例：
- 输入：nums = [1,1,2]
- 输出： [[1,1,2], [1,2,1], [2,1,1]]
这道题目和上述全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列，这里又涉及到去重了。
这里的去重和组合去重方式一样，类比组合总和2的去重方式。
回溯程序设计
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used)
{if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); i++){// 排列需要记录元素的使用情况if ( i > 0 && nums[i] == nums[i-1] && used[i-1] == false || used[i] == true)continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used);path.pop_back();used[i] = false;}return;
}