1--回溯算法理论基础
回溯算法本质上是一个暴力搜索的过程，其常用于解决组合、切割、子集、排列等问题，其一般模板如下：
void backTracking(参数){if(终止条件){// 1. 收获结果;// 2. return;}for(..遍历){// 1. 处理节点// 2. 递归搜索// 3. 回溯 // 即撤销对节点的处理}return;
}2--组合问题
主要思路：
基于回溯法，暴力枚举 k 个数，需注意回溯弹出元素的操作；
#include <iostream>
#include <vector>class Solution {
public:std::vector<std::vector<int>> combine(int n, int k) {std::vector<int> path;backTracking(n, k, path, 1); // 从第 1 个数开始return res;}void backTracking(int n, int k, std::vector<int> path, int start){if(path.size() == k){res.push_back(path);return;}for(int i = start; i <= n; i++){path.push_back(i);backTracking(n, k, path, i + 1); // 递归暴力搜索下一个数path.pop_back(); // 回溯}}private:std::vector<std::vector<int>> res;
};int main(int argc, char* argv[]){int n = 4, k = 2;Solution S1;std::vector<std::vector<int>> res = S1.combine(n, k);for(auto v : res){for(int item : v) std::cout << item << " ";std::cout << std::endl;}return 0;
}3--组合问题的剪枝操作
上题的组合问题中，对于进入循环体 for(int i = start; i <= n; i++)：
已选择的元素数量为：path.size()
仍然所需的元素数量为：k - path.size()
剩余的元素集合为：n - i + 1
则为了满足要求，必须满足：k-path.size() <= n - i + 1，即 i <= n - k + path.size() + 1
因此，可以通过以下条件完成剪枝操作：
for(int i = start; i <= i <= n - k + path.size() + 1; i++)
#include <iostream>
#include <vector>class Solution {
public:std::vector<std::vector<int>> combine(int n, int k) {std::vector<int> path;backTracking(n, k, path, 1); // 从第 1 个数开始return res;}void backTracking(int n, int k, std::vector<int> path, int start){if(path.size() == k){res.push_back(path);return;}for(int i = start; i <= n - k + path.size() + 1; i++){path.push_back(i);backTracking(n, k, path, i + 1); // 暴力下一个数path.pop_back(); // 回溯}}private:std::vector<std::vector<int>> res;
};int main(int argc, char* argv[]){int n = 4, k = 2;Solution S1;std::vector<std::vector<int>> res = S1.combine(n, k);for(auto v : res){for(int item : v) std::cout << item << " ";std::cout << std::endl;}return 0;
}4--组合总和III
主要思路：
类似于上面的组合问题，基于回溯来暴力枚举每一个数，需要注意剪枝操作；
#include <iostream>
#include <vector>class Solution {
public:std::vector<std::vector<int>> combinationSum3(int k, int n) {std::vector<int> path;backTracking(k, n, 0, path, 1);return res;}void backTracking(int k, int n, int sum, std::vector<int>path, int start){if(sum > n) return; // 剪枝if(path.size() == k){ // 递归终止if(sum == n){res.push_back(path);}return;}for(int i = start; i <= 9 + path.size() - k + 1; i++){ // 剪枝path.push_back(i);sum += i;backTracking(k, n, sum, path, i + 1); // 递归枚举下一个数// 回溯sum -= i;path.pop_back();}}
private:std::vector<std::vector<int>> res;
};int main(int argc, char* argv[]){int k = 3, n = 7;Solution S1;std::vector<std::vector<int>> res = S1.combinationSum3(k, n);for(auto v : res){for(int item : v) std::cout << item << " ";std::cout << std::endl;}return 0;
}5--电话号码的字母组合
主要思路：
根据传入的字符串，遍历每一个数字字符，基于回溯法，递归遍历每一个数字字符对应的字母；
#include <iostream>
#include <vector>
#include <string>class Solution {
public:std::vector<std::string> letterCombinations(std::string digits) {if(digits.length() == 0) return res;std::vector<std::string> letter = {"", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backTracking(digits, letter, 0);return res;}void backTracking(std::string digits, std::vector<std::string> letter, int cur){if(cur == digits.size()){res.push_back(tmp);return;}int letter_idx = digits[cur] - '0';int letter_size = letter[letter_idx].size();for(int i = 0; i < letter_size; i++){tmp.push_back(letter[letter_idx][i]);backTracking(digits, letter, cur+1);// 回溯tmp.pop_back();}}private:std::vector<std::string> res;std::string tmp;
};int main(int argc, char* argv[]){std::string test = "23";Solution S1;std::vector<std::string> res = S1.letterCombinations(test);for(std::string str : res) std::cout << str << " ";std::cout << std::endl;return 0;
}6--组合总和
主要思路：
经典组合问题，通过回溯法暴力递归遍历；
#include <iostream>
#include <vector>class Solution {
public:std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {if(candidates.size() == 0) return res;backTracking(candidates, target, 0, 0, path);return res;}void backTracking(std::vector<int>& candidates, int target, int sum, int start, std::vector<int>path){if(sum > target) return; // 剪枝if(sum == target) {res.push_back(path);return;}for(int i = start; i < candidates.size(); i++){sum += candidates[i];path.push_back(candidates[i]);backTracking(candidates, target, sum, i, path);// 回溯sum -= candidates[i];path.pop_back();}}private:std::vector<std::vector<int>> res;std::vector<int> path;
};int main(int argc, char* argv[]){// candidates = [2,3,6,7], target = 7std::vector<int> test = {2, 3, 6, 7};int target = 7;Solution S1;std::vector<std::vector<int>> res = S1.combinationSum(test, target);for(auto vec : res){for(int val : vec) std::cout << val << " ";std::cout << std::endl; }return 0;
}7--组合总和II
主要思路：
基于回溯法，暴力递归遍历数组；
本题不能包含重复的组合，但由于有重复的数字，因此需要进行树层上的去重；
#include <iostream>
#include <vector>
#include <algorithm>class Solution {
public:std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {if(candidates.size() == 0) return res;std::sort(candidates.begin(), candidates.end());std::vector<bool> visited(candidates.size(), false);backTracking(candidates, target, 0, 0, visited);return res;}void backTracking(std::vector<int>& candidates, int target, int sum, int start, std::vector<bool>& visited){if(sum > target) return; // 剪枝if(sum == target){res.push_back(path);return;}for(int i = start; i < candidates.size(); i++){// 树层剪枝去重if(i > 0 && candidates[i-1] == candidates[i]){if(visited[i-1] == false) continue;}sum += candidates[i];path.push_back(candidates[i]);visited[i] = true;backTracking(candidates, target, sum, i+1, visited);// 回溯sum -= candidates[i];path.pop_back();visited[i] = false;}}private:std::vector<std::vector<int>> res;std::vector<int> path;
};int main(int argc, char* argv[]){// candidates = [10,1,2,7,6,1,5], target = 8std::vector<int> test = {10, 1, 2, 7, 6, 1, 5};int target = 8;Solution S1;std::vector<std::vector<int>> res = S1.combinationSum2(test, target);for(auto vec : res){for(int val : vec) std::cout << val << " ";std::cout << std::endl; }return 0;
}
![[Linux]动静态库](https://img-blog.csdnimg.cn/img_convert/e275ac4cd796029cfb49e93ce8c23945.png)
