回溯法解题框架

回溯问题就是一个决策树的遍历过程

考虑三个问题：

路径：也就是已经做出的选择选择列表：当前可以做的选择结束条件：到达决策树的底层，无法再做选择的条件

回溯法框架

result[] def backtrack() if满足结束条件 添加路径 return for 选择in选择列表 选择 backtrack（） 撤回选择

全排列问题（不包含重复数字）

路径就是已经做过的选择，选择列表就是当前可以做的选择，结束条件就是遍历到树的底层也就是选择列表为空的时候。 通过算法框架写出代码（用list时间效率比vector高）

class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<int>track; if(nums.size()<1) return res; backtrack(nums,track); return res; } void backtrack(vector<int>&nums,vector<int>track) { //if满足决策条件 if(track.size()==nums.size()) { //添加路径 res.push_back(track); //return return; } //for 选择 in 选择列表 for(auto num:nums) { //做选择 auto ishave=find(track.begin(),track.end(),num); if(ishave==track.end()) { track.push_back(num); //backtrack() backtrack(nums,track); //撤销选择 track.pop_back(); } else continue; } } private: vector<vector<int>>res; };

N皇后问题

这个问题很经典了，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。 PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。 这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。 直接套用框架:

class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<string>board(n,string(n,'.')); if(n<1)return res; backtrack(0,board);//细节错误，0写成了n找了很久 return res; } void backtrack(int row,vector<string>board) { //if满足结束条件 if(row==board.size()) { //添加结果 res.push_back(board); //return return; } //for 选择in选择列表 for(int i=0;i<board.size();i++) { //判断选择 if(isvalid(board,row,i)) { board[row][i]='Q'; //backtrack(row+1,board) backtrack(row+1,board); //撤销选择 board[row][i]='.'; } } } bool isvalid(vector<string>board,int row,int col)//只要判断当前节点上、左上和右上这三个方向就可以了 { for(int currow=0;currow<board.size();currow++)//判断一列 { if(board[currow][col]=='Q') return false; } for(int currow=row-1,curcol=col-1;currow>=0&&curcol>=0;currow--,curcol--) { if(board[currow][curcol]=='Q') return false; } for(int currow=row-1,curcol=col+1;currow>=0&&curcol<board.size();currow--,curcol++) { if(board[currow][curcol]=='Q') return false; } return true; } private: vector<vector<string>>res; };

动态规划：状态 dp定义 选择 base case 回溯：路径 选择 结束条件 某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。

例题

1.组合总和

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ] 套用框架 result[] def backtrack() if结束条件 result.add(track) return; for 选择in选择列表 选择 backtrack() 撤销选择 发现有重复组合（解集的各种排列组合） 解决：首先对原始数组进行排序；用一个索引数组标识路径中已有的索引；用prenum记录每一次选择循环当前元素的前一个元素，如果重复就剪去这个元素；用fathernum记录上一个路径节点，判断子节点如果小于父节点就剪去这个元素； class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<int>nums=candidates; sort(nums.begin(),nums.end()); vector<int>track; vector<bool>havevisit(candidates.size(),false); backtrack(nums,havevisit,track,target,0); return res; } void backtrack(vector<int>& nums,vector<bool>&havevisit,vector<int>track,int target,int fathernum) { int prenum=0; //if结束条件 if(target==0) { //添加路径 res.push_back(track); //return return; } else if(target<0) return; for(int i=0;i<nums.size();i++) { if(nums[i]==prenum||havevisit[i]==true||nums[i]<fathernum) continue; else { havevisit[i]=true; prenum=nums[i]; track.push_back(nums[i]); backtrack(nums,havevisit,track,target-nums[i],nums[i]); track.pop_back(); havevisit[i]=false; } } //for 选择in选择列表 //选择 //backtrack //撤销选择 } private: vector<vector<int>> res; }; 优化：发现时间复杂度和空间复杂度都很高,想用哈希表替代排序、 class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { //vector<int>nums=candidates; //sort(nums.begin(),nums.end()); vector<int>track; vector<bool>havevisit(candidates.size(),false); backtrack(candidates,havevisit,track,target,0); return res; } void backtrack(vector<int>& nums,vector<bool>&havevisit,vector<int>track,int target,int fathernum) { //int prenum=0; //if结束条件 if(target==0) { //添加路径 res.push_back(track); //return return; } else if(target<0) return; unordered_set<int> Myset; for(int i=0;i<nums.size();i++) { //if(nums[i]==prenum||havevisit[i]==true||nums[i]<fathernum) if(Myset.find(nums[i])!=Myset.end()||havevisit[i]==true||nums[i]<fathernum) continue; else { havevisit[i]=true; Myset.insert(nums[i]); track.push_back(nums[i]); backtrack(nums,havevisit,track,target-nums[i],nums[i]); track.pop_back(); havevisit[i]=false; } } //for 选择in选择列表 //选择 //backtrack //撤销选择 } private: vector<vector<int>> res; };

时间复杂度反而更高

2.有重复字符串的排列组合

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。 示例1: 输入：S = "qqe" 输出：["eqq","qeq","qqe"] 示例2: 输入：S = "ab" 输出：["ab", "ba"] 提示: 字符都是英文字母。 字符串长度在[1, 9]之间。 回溯法框架 //result[] //def backtrack //if 结束条件 //result.add(track) //return; //for 选择in选择列表 //选择 //backtrack //撤回选择 class Solution { public: vector<string> permutation(string S) { string track; vector<bool>hasInTrack(S.size(), false); backtrack(S, track, hasInTrack); return result; } void backtrack(string s, string & track, vector<bool>&hasInTrack) { int n = s.size(); if (track.size() >= s.size()) { result.push_back(track); return; } unordered_set<char>hasappear; for (int i = 0; i < n; i++) { if (auto iter = hasappear.find(s[i]) == hasappear.end()&& hasInTrack[i] == false) { hasappear.insert(s[i]); hasInTrack[i] = true; track.push_back(s[i]); backtrack(s, track, hasInTrack); track.pop_back(); hasInTrack[i] = false; } else continue; } } private: vector<string>result; };

减枝问题 1.已经存在于路径的节点:用一个数组记录哪一个位置的元素已被访问过，需要回溯 2.同一层的节点避免重复:用一个哈希表记录for循环时哪些元素是重复的