回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。
当探索到某一步时，发现原先选择并不优或 达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。也可以称为剪枝点，所谓的剪枝，指的是把不会找到目标，或者不必要的路径裁剪掉。
从上面看出，回溯其实就是选优搜索法，按照深度优先搜索的方式进行搜索，再通过剪枝来避免不相关结果。
//模板 回溯() { if(满足结束条件) { 将结果加入结果集中 return; } for(当前选择 : 选择列表) { 1.完成这一步的选择 2.回溯(下一步), 进行下一步的选择 3.撤销选择，继续进行其他尝试 } }给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
DFS + 回溯，如果当前组合行不通则回溯到上一步，然后继续尝试其他组合。
class Solution { public: vector<string> numToStr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; //数字——字母映射 void DFS(vector<string>& res, string& digits, string cur, int index) { //此时数字已遍历结束 if(index == digits.size()) { //如果组合不为空，则加入结果集中 if(!cur.empty()) { res.push_back(cur); return; } } //搜索当前所有可能的组合 for(auto ch : numToStr[digits[index] - '0']) { cur.push_back(ch); DFS(res, digits, cur, index + 1); //回溯到上一步的状态 cur.pop_back(); } } vector<string> letterCombinations(string digits) { if(digits.empty()) { return {}; } vector<string> res; DFS(res, digits, "", 0); return res; } };二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。
例如，上面的二进制手表读取 “3:25”。
给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-watch
和上题思路一样，不过变为了组合二进制。
class Solution { public: vector<int> nToTime = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32}; void DFS(vector<string>& res, int num, int index, pair<int, int>& time) { //如果没有剩余的灯，就返回 if(num == 0) { if(time.first > 11 || time.second > 59) { return; } string cur = (to_string(time.first) + ":"); if(time.second < 10) //小于10要补0 { cur += '0'; } cur += to_string(time.second); res.push_back(cur); //组合结果 return; } //尝试当前每一种组合 for(int i = index; i < 10; i++) { //超出范围,舍弃该数据 if(time.first > 11 || time.second > 59) { continue; } pair<int, int> backUp = time; //前四个灯为小时 if(i < 4) { time.first += nToTime[i]; } //后六个灯为分钟 else { time.second += nToTime[i]; } DFS(res, num - 1, i + 1, time); //进入下一层搜索, 下次从第i + 1栈灯开始 time = backUp; //回溯状态 } } vector<string> readBinaryWatch(int num) { vector<string> res; pair<int, int> time(0, 0); DFS(res, num, 0, time); return res; } };给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。 解集不能包含重复的组合。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum
和上面的思路一样，不过此时由于数据可以无限被选取，所以搜索时下一步的位置还是从当前位置i开始，不需要继续推进。(这道题目也可以当成完全背包，与动态规划题解中的零钱问题II类似)
class Solution { public: void DFS(vector<int>& candidates, vector<vector<int>>& res, vector<int>& cur, int target, int sum, int index) { //如果大于等于target，则不可再增加 if(sum >= target) { //如果和target相等则返回结果集 if(sum == target) { res.push_back(cur); } return; } //尝试当前各种结果 for(int i = index; i < candidates.size(); i++) { //如果当前元素比target大,则不可能成立，直接跳过 if(candidates[i] > target) { continue; } cur.push_back(candidates[i]); DFS(candidates, res, cur, target, sum + candidates[i], i); //由于此时数据可以被无限选取，所以下一步的位置继续从i开始搜索 cur.pop_back(); //回溯 } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { if(candidates.empty()) { return {}; } vector<vector<int>> res; vector<int> cur; DFS(candidates, res, cur, target, 0, 0); return res; } };给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
照着模板就可以写出来
class Solution { public: void DFS(vector<vector<int>>& allRet, vector<int>& curRet, vector<int>& nums, vector<bool>& visited) { //满足条件则加入结果集 if(curRet.size() == nums.size()) { allRet.push_back(curRet); } for(int i = 0; i < nums.size(); i++) { //跳过以访问数字 if(visited[i] == false) { continue; } //记录当前结果 curRet.push_back(nums[i]); visited[i] = false; //进行下一步的搜索 DFS(allRet, curRet, nums, visited); //回溯 curRet.pop_back(); visited[i] = true; } } vector<vector<int>> permute(vector<int>& nums) { if(nums.empty()) { return {}; } vector<vector<int>> allRet; vector<int> curRet; vector<bool> visited(nums.size(), true); DFS(allRet, curRet, nums, visited); return allRet; } };你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。
注意：本题中，每个活字字模只能使用一次。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-tile-possibilities
全排列的变形，此时变为处理字符串，并且返回任意可以印出的组合
1.当前组合不为空, 则插入set中
2.继续给当前组合拼接新的组合，尝试拼接tiles每一个位置的字符
3.如果当前位置已在组合中出现过，跳过该位置，否则标记当前位置，继续拼接更长的组合
4.回溯，尝试组合其它位置，返回
class Solution { public: void DFS(unordered_set<string>& set, vector<bool>& visited, string& tiles, string cur) { //结果不为空则记录下来 if(!cur.empty()) { set.insert(cur); } for(int i = 0; i < tiles.size(); i++) { //如果当前字模已经用过, 则跳过本轮 if(visited[i] == false) { continue; } //记录当前位 cur.push_back(tiles[i]); visited[i] = false; //查找下一位 DFS(set, visited, tiles, cur); //回溯, 继续尝试其他组合 visited[i] = true; cur.pop_back(); } } int numTilePossibilities(string tiles) { if(tiles.empty()) { return 0; } unordered_set<string> set; //结果集, 去重 vector<bool> visited(tiles.size(), true); //标记矩阵 DFS(set, visited, tiles, ""); return set.size(); } };n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens
具体思路看注释，主要就是尝试所有排列组合，并判断行，列，左右对角线是否存在其他皇后，然后将所有符合条件的结果保存下来即可。
class Solution { public: void DFS(vector<vector<pair<int, int>>>& allRes, vector<pair<int, int>>& curRes, int curRow, int n) { //此时说明已经走完, 记录结果 if(curRow == n) { allRes.push_back(curRes); } for(int i = 0; i < n; i++) { //如果当前符合规则, 则继续, 如果不符合直接忽略 if(isVaild(curRes, curRow, i)) { //记录当前行位置 curRes.push_back(make_pair(curRow, i)); //查找下一行 DFS(allRes, curRes, curRow + 1, n); //回溯 curRes.pop_back(); } } } bool isVaild(vector<pair<int, int>>& curRes, int row, int col) { //判断当前位置是否合法, 各皇后不能放在同一条直线上 for(const pair<int, int>& cur : curRes) { if(cur.first == row //判断当前行 || cur.second == col //判断当前列 || cur.first + cur.second == row + col //判断左对角线 || cur.first - cur.second == row - col) //判断右对角线 { return false; } } return true; } //将坐标结果转换为字符串的棋盘 vector<vector<string>> resToString(vector<vector<pair<int, int>>>& allRes, int n) { vector<vector<string>> res; for(const vector<pair<int, int>>& cur : allRes) { vector<string> curRes(n, string(n, '.')); //初始化棋盘 for(const pair<int, int>& pos : cur) //将皇后放入棋盘中 { curRes[pos.first][pos.second] = 'Q'; } res.push_back(curRes); //保存结果 } return res; } vector<vector<string>> solveNQueens(int n) { vector<vector<pair<int, int>>> allRes; vector<pair<int, int>> curRes; DFS(allRes, curRes, 0, n); return resToString(allRes, n); } };n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-queens-ii
和上题思路一样，因为只需要返回解决方案的数量，所以不再保存结果，对符合条件的情况进行计数即可。
class Solution { public: void DFS(vector<pair<int, int>>& curRes, int curRow, int n, int& count) { //此时不需要保存结果, 计数就行 if(curRow == n) { ++count; } for(int i = 0; i < n; i++) { //如果当前符合规则, 则继续, 如果不符合直接忽略 if(isVaild(curRes, curRow, i)) { //记录当前行位置 curRes.push_back(make_pair(curRow, i)); //查找下一行 DFS(curRes, curRow + 1, n, count); //回溯 curRes.pop_back(); } } } bool isVaild(vector<pair<int, int>>& curRes, int row, int col) { //判断当前位置是否合法, 各皇后不能放在同一条直线上 for(const pair<int, int>& cur : curRes) { if(cur.first == row //判断当前行 || cur.second == col //判断当前列 || cur.first + cur.second == row + col //判断左对角线 || cur.first - cur.second == row - col) //判断右对角线 { return false; } } return true; } int totalNQueens(int n) { vector<pair<int, int>> curRes; int count = 0; DFS(curRes, 0, n, count); return count; } };