本文主要是介绍回溯算法题解（难度由小到大）（力扣，洛谷），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
注意：
P1157 组合的输出（洛谷）https://www.luogu.com.cn/problem/P1157int result[10000] = { 0 };
216. 组合总和 IIIhttps://leetcode.cn/problems/combination-sum-iii/
17. 电话号码的字母组合https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
39. 组合总和https://leetcode.cn/problems/combination-sum/
40. 组合总和 IIhttps://leetcode.cn/problems/combination-sum-ii/
131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/
93. 复原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/
78. 子集https://leetcode.cn/problems/subsets/
90. 子集 IIhttps://leetcode.cn/problems/subsets-ii/
491.非递减子序列
46. 全排列https://leetcode.cn/problems/permutations/
47. 全排列 IIhttps://leetcode.cn/problems/permutations-ii/
P1219 [USACO1.5] 八皇后 Checker Challengehttps://www.luogu.com.cn/problem/P1219
51. N 皇后https://leetcode.cn/problems/n-queens/
37. 解数独https://leetcode.cn/problems/sudoku-solver/
✨欢迎来到脑子不好的小菜鸟的文章✨
🎈创作不易，麻烦点点赞哦🎈
所属专栏：刷题_脑子不好的小菜鸟的博客-CSDN博客
我的主页：脑子不好的小菜鸟
文章特点：关键点和步骤讲解放在
代码相应位置
注意：
本篇由易到难，若想做难题，可移步至该文章：过去一周写过的算法题的一部分（dfs，贪心）-CSDN博客
P1157 组合的输出（洛谷）
https://www.luogu.com.cn/problem/P1157int result[10000] = { 0 };
void dfs(int n, int r, int size, int start){int i;//终止条件if (size == r){for (i = 0; i < size; i++){printf("%3d", result[i]);}printf("\n");return;}//单层递归逻辑for (i = start; i <= n - (r - size) + 1; i++)//剪枝{result[size] = i;dfs(n, r, size + 1, i + 1);}
}
int main(){int n, r;scanf("%d%d", &n, &r);dfs(n, r, 0, 1);return 0;
}216. 组合总和 III
https://leetcode.cn/problems/combination-sum-iii/
class Solution {
public:vector<vector<int>>result;vector<int>path;void backtracking(int k, int n, int sum, int start){if (sum > n || start > n) return;if (sum == n && path.size() == k){result.push_back(path);return;}int i;for (i = start; i <= 9; i++)//可优化(剪枝){path.push_back(i);if (sum + i <= n) backtracking(k, n, sum + i, i + 1);path.pop_back();}return;}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 0, 1);return result;}
};17. 电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
//注意是组合，不是排列
//需要先将各个按键代表的字符串记录---->枚举常量//该题注意：
//1.C++中的类似C语言中枚举的定义方式
//2.对枚举的常量的调用
class Solution {
public:const string/**/ lettermap[10]/**/ =/**/ {"","",//这两行不能省，否则按0，1这两种情况解决不了"abc" ,"def","ghi","jkl","mno","pqrs","tuv","wxyz",/**/};vector<string>result;string path;void backtracking(string digits, int index){if (path.size() == digits.size())/**/{result.push_back(path);return;}int digit = digits[index] - '0';int i;for (i = 0; i < lettermap[digit].size(); i++){path.push_back(lettermap[digit][i]);backtracking(digits, index + 1);path.pop_back();}}vector<string> letterCombinations(string digits) {if (digits.size() == 0) return result;backtracking(digits, 0);return result;}
};39. 组合总和
https://leetcode.cn/problems/combination-sum/
//与之前的组合问题不同的是：这需要在每一个节点判断结果，而不是叶子节点class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& candidates, int target, int sum, int start){if (sum > target) return;if (sum == target){result.push_back(path);return;}int i;for (i = start; i < candidates.size(); i++){path.push_back(candidates[i]);if (sum + candidates[i] <= target) backtracking(candidates, target, sum + candidates[i], i/*注意是i，不是i + 1*/);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates, target, 0, 0);return result;}
};40. 组合总和 II
https://leetcode.cn/problems/combination-sum-ii/
//map是find键，而不是值
//unordered_map<vector<int>, int>map;要自己构造哈希函数/*！！！该题重点：不能有重复的集合----->树层去重，树枝去重
树层去重目的：不出现相同的组合（用used数组）
树枝去重目的：一个数不被用两次（用start控制起始下标）
！！！！*/class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& candidates, int target, int sum, int start, vector<bool>& used){if (sum == target){result.push_back(path);return;}int i;for (i = start; i < candidates.size(); i++){if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false/***不是true,若为true,说明是同一树枝，而不是树层***/)continue;path.push_back(candidates[i]);used[i] = true;if (sum + candidates[i] <= target) backtracking(candidates, target, sum + candidates[i], i + 1, used);used[i] = false;path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};131. 分割回文串
https://leetcode.cn/problems/palindrome-partitioning/
//重点：分割字符串
//注意strsub（分割字符串）的使用：strsub(string s, 起始坐标，分割的字母个数);class Solution {
public:vector<vector<string>>result;vector<string>str;bool ishuiwen(string& s, int start, int end){int i = start, j = end;while (i < j){if (s[i] != s[j])return false;i++;j--;}return true;}void backtracking(string& s, int start){if (start >= s.size()){result.push_back(str);return;}int i;for (i = start; i < s.size(); i++){if (ishuiwen(s, start, i)){string temp = s.substr(start, i - start + 1);str.push_back(temp);backtracking(s, i + 1);str.pop_back();}elsecontinue;}}vector<vector<string>> partition(string s) {if (s.size() == 0) return result;backtracking(s, 0);return result;}
};93. 复原 IP 地址
https://leetcode.cn/problems/restore-ip-addresses/
//该题不要path,直接在s里加'.'
//注意insert和erase的使用class Solution {
public:vector<string>result;bool islegal(string& s, int start, int end){if (s[start] == '0' && end - start != 0)return false;int sum = 0;int i;for (i = start; i <= end; i++){if (s[i] < '0' && s[i] > '9')return false;sum = sum * 10 + (s[i] - '0');if (sum > 255)/******要放在for循环里面*****/return false;}return true;}void backtracking(string& s, int num, int start){if (num == 3){if (islegal(s, start, s.size() - 1)){result.push_back(s);}return;}int i;for (i = start; i < s.size(); i++){if (islegal(s, start, i) && i + 1 != s.size()/*******/){s.insert(s.begin() + i + 1, '.');// string temp = s.substr(start, i - start + 1);// path.push_back(temp);// path.push_back('.');backtracking(s, num + 1, i + 1 + 1/*注意不是i + 1*/);// path.pop_back();s.erase(s.begin() + i + 1);}elsebreak;/******/}}vector<string> restoreIpAddresses(string s) {if (s.size() < 4 || s.size() > 12)return result;backtracking(s, 0, 0);return result;}
};78. 子集
https://leetcode.cn/problems/subsets/
class Solution {
public:vector<vector<int>>result;vector<int>path;void backtracking(vector<int>& nums, int start){result.push_back(path);int i;for (i = start; i < nums.size(); i++){path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};90. 子集 II
https://leetcode.cn/problems/subsets-ii/
//注意点：解集 不能 包含重复的子集------>涉及树层的去重问题class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& nums, vector<int>& used, int start){result.push_back(path);int i;for (i = start; i < nums.size(); i++){if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)/*树层去重的关键*/continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used, i + 1);path.pop_back();used[i] = false;}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());/*树层去重的关键！！！！！！！！！！！*/vector<int>used(nums.size(), false);backtracking(nums, used, 0);return result;}
};491.非递减子序列
注意：
放入答案时要注意其大小和path中最后一个元素的大小，注意是path的最后一个，而不是数组的前一个
https://leetcode.cn/problems/non-decreasing-subsequences/
//注意unordered_set的使用，与map不同，加入是insert,查找不可用下标
//注意查看vector的最后一个元素不可用下标，而是vector.back()class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& nums/*, vector<int>& used*/, int start){if (path.size() >= 2)result.push_back(path);unordered_set<int>uset;/**!!!!!!!!!!!!!!!!!!*/int i;for (i = start; i < nums.size(); i++){/*注意使用path.back()时要检查path是否为空*/if (!path.empty() && nums[i] < path.back())continue;/*[10,1,1,1,1,1]过不了，因为这题没有排序，而是按照之前的顺序，因此比较nums[i]和nums[i-1]没用*/// if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)/*树层去重的关键*/// continue;if (uset.find(nums[i]) != uset.end())/*树层去重的关键*/continue;path.push_back(nums[i]);uset.insert(nums[i]);backtracking(nums, i + 1);path.pop_back();// uset[nums[i]] = 0;(不用,因为退出该层就重新创建了)}}vector<vector<int>> findSubsequences(vector<int>& nums) {// vector<int>used(nums.size(), false);// backtracking(nums, used, 0);backtracking(nums, 0);return result;}
};46. 全排列
https://leetcode.cn/problems/permutations/
class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& nums, vector<int>& used){if (path.size() == nums.size()){result.push_back(path);return;}int i;for (i = 0; i < nums.size(); i++){if (used[i] == 1)continue;path.push_back(nums[i]);used[i] = 1;backtracking(nums, used);path.pop_back();used[i] = 0;}}vector<vector<int>> permute(vector<int>& nums) {if (nums.size() == 0)return result;vector<int> used(nums.size(), 0);/*一定要初始化*/backtracking(nums, used);return result;}
};47. 全排列 II
https://leetcode.cn/problems/permutations-ii/
//又涉及树层去重class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(vector<int>& nums, vector<int>& used){if (path.size() == nums.size()){result.push_back(path);return;}int i;for (i = 0; i < nums.size(); i++){if (i > 0 && nums[i] == nums[i-1] && used[i - 1] == 0)continue;if (used[i] == 1)/*不能少*/continue;path.push_back(nums[i]);used[i] = 1;backtracking(nums, used);path.pop_back();used[i] = 0;}}vector<vector<int>> permuteUnique(vector<int>& nums) {if (nums.size() == 0)return result;sort(nums.begin(),nums.end());vector<int> used(nums.size(), 0);/*一定要初始化*/backtracking(nums, used);return result;}
};P1219 [USACO1.5] 八皇后 Checker Challenge
https://www.luogu.com.cn/problem/P1219
int count = 0, ans[50] = { 0 }, lie[50] = { 0 }, dui[50] = { 0 }, fandui[17] = { 0 };
void dfs(int n, int row)
{int i;if (row == n + 1)/*注意是n + 1啊*/{count++;if (count <= 3){for (i = 0; i < n; i++)printf("%d ", ans[i]);printf("\n");}return;}for (i = 1; i <= n; i++)//列{if (lie[i] == 1 || dui[i + row] == 1 || fandui[i - row + n] == 1)continue;lie[i] = 1;dui[i + row] = 1;fandui[i - row + n] = 1;ans[row - 1] = i;dfs(n, row + 1);lie[i] = 0;dui[i + row] = 0;fandui[i - row + n] = 0;}
}int main()
{int n;scanf("%d", &n);dfs(n, 1);printf("%d\n", count);return 0;
}51. N 皇后
https://leetcode.cn/problems/n-queens/
//注意主对角线和副对角线的行列之间的关系/*
<0,0> <0,1> <0,2><1,0> <1,1> <1,2><2,0> <2,1> <2,2>
*///主对角线：y - x相等------>注意可能是负数：至少要加上n - 1---->可能和主对角线的标记重复----->都加上n - 1
//副 ：y + x相等class Solution {
public:vector<vector<string>> res;bool isValid(int row, int col, int n, std::vector<std::string> path){int i, j;for (i = 0; i < n; i++){for (j = 0; j < n; j++){if (j == col && path[i][j] == 'Q')return false;if ((i + j == row + col && path[i][j] == 'Q') || (-i + j == -row + col && path[i][j] == 'Q'))return false;}}return true;}void backtracking(int n, int size, std::vector<std::string> path){if (size == n){res.push_back(path);return;}int i, j;for (j = 0; j < n; j++){if (isValid(size, j, n,path)){path[size][j] = 'Q';backtracking(n, size + 1,path);path[size][j] = '.';}}}vector<vector<string>> solveNQueens(int n) {//表示的是：path是一个装满string的容器，容器被初始化为有n个元素，每个元素是string，string被初始化为长度为n的.//：：是一个作用域解析运算符，用于指定一个名称在哪个命名空间或类中定义的//std ---->using namespace std;//用了叫做std的命名空间std::vector<std::string> path(n, std::string(n, '.'));/*先全部初始化为'.'*/backtracking(n, 0, path);return res;}
};37. 解数独
https://leetcode.cn/problems/sudoku-solver/
class Solution {
public:bool isValid(vector<vector<char>>& board, int row, int col, char ch){int i, j;for (i = 0; i < board.size(); i++){for (j = 0; j < board[0].size(); j++){if (i == row && board[i][j] == ch)return false;if (j == col && board[i][j] == ch)return false;}}int startx = row / 3 * 3;int starty = col / 3 * 3;for (i = startx; i < startx + 3; i++){for (j = starty; j < starty + 3; j++){if (board[i][j] >= '1' && board[i][j] <= '9' && board[i][j] == ch)return false;}}return true;}//该题没有终止条件也没事，因为两层循环进行完了就会结束bool backtracking(vector<vector<char>>& board){int i, j;for (i = 0; i < board.size(); i++){for (j = 0; j < board[0].size(); j++){if (board[i][j] <= '9' && board[i][j] >= '1')continue;for (char ch = '1'; ch <= '9'; ch++){if (isValid(board, i, j, ch)){board[i][j] = ch;if(backtracking(board))/*只要一种结果---->找到就立马返回---->递归函数要有返回值*/return true;board[i][j] = '.';}}return false;//9个数都试完了，都没找到}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);}看完了记得关注我哦：脑子不好的小菜鸟
以后共同进步，该账号会发布项目，算法，知识点等内容
这篇关于回溯算法题解（难度由小到大）（力扣，洛谷）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
