回溯算法原理
回溯和递归是相辅相成的，只要由递归就会有回溯，回溯函数等于递归函数。
回溯搜索算法就是一种纯暴力搜索，在一些问题无法通过暴力搜索得到，智能依靠回溯，回溯算法解决的问题有：
- 组会：找到大小为多少的组合
- 切割：对一个字符串进行切割，切割成多个子串，这些子串都符合回文子串
- 子集：把子集列出来
- 排列：排列是强调元素顺序，组合没有顺序
- 棋盘问题：n皇后问题，解数独
回溯算法的思路：首先一个问题要看成一个n叉树，宽度等于几何的大小（可以用for循环遍历），纵方向使用递归处理。
回溯算法模版
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
77.组合
77. 组合 - 力扣（LeetCode）
问题:
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路：把问题抽象成n叉树，不重复取值，每次从元素中取值，选择范围随着可选择的元素而收缩，调整可选择范围。在n叉树中，每次搜索到了叶子结点，我们就能得到一个结果。
回溯法的三部曲：
- 递归函数的参数及返回值
- 回溯函数的终止条件
- 单层搜索的过程
class Solution {
private:
vector<vector<int>> reslut;
vector<int> path;
void backTracking(int n , int k , int startIndex){
if(path.size() == k){
reslut.push_back(path);
return;
}
for(int i = startIndex ; i <= n ;i++){
path.push_back(i);
backTracking(n , k , i+1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
reslut.clear();
path.clear();
backTracking(n , k , 1);
return reslut;
}
};
剪枝优化版
class Solution {
private:
vector<vector<int>> reslut;
vector<int> path;
void backTracking(int n , int k , int startIndex){
if(path.size() == k){
reslut.push_back(path);
return;
}
for(int i = startIndex ; i <= n - (k - path.size()) + 1;i++){
path.push_back(i);
backTracking(n , k , i+1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
reslut.clear();
path.clear();
backTracking(n , k , 1);
return reslut;
}
};
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
216.组合总和
216. 组合总和 III - 力扣（LeetCode）
问题：
找出所有相加之和为 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]]
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backTracking(int target , int k , int sum ,int satrtIndex){
if(path.size() == k){
if(sum == target )result.push_back(path);
return;
}
for(int i = satrtIndex ; i <= 9 ;i++){
sum+=i;
path.push_back(i);
backTracking(target , k , sum , i+1);
sum-=i;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backTracking(n,k,0,1);
return result;
}
};
剪枝优化版
class Solution {
private:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (sum > targetSum) { // 剪枝操作
return;
}
if (path.size() == k) {
if (sum == targetSum) result.push_back(path);
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
sum += i; // 处理
path.push_back(i); // 处理
backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
sum -= i; // 回溯
path.pop_back(); // 回溯
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
result.clear(); // 可以不加
path.clear(); // 可以不加
backtracking(n, k, 0, 1);
return result;
}
};
17.电话号码的字母组合
17. 电话号码的字母组合 - 力扣（LeetCode）
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector<string> result;
string s;
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - '0'; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]); // 处理
backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了
s.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
s.clear();
result.clear();
if (digits.size() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
};
