回溯算法

• 回溯法的经典题目
• 图解如下图所示:

class Solution {
public:vector<int>path;// 选取的组合vector<vector<int>>ret;// 最终结果// 用startIndex来记录下一层递归搜索的起始位置// 防止重现重复的组合void backtracking(int n ,int k ,int startIndex){if(path.size() == k){ret.push_back(path);// 收集结果return ;}for(int i = startIndex;i <= n;i++){// 横向遍历path.push_back(i);// 添加backtracking(n,k,i+1);// 纵向遍历path.pop_back();// 撤销}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return ret;}
};

• 剪枝优化，将for循环控制条件改为

class Solution {
public:vector<int>path;// 选取的组合vector<vector<int>>ret;// 最终结果// 用startIndex来记录下一层递归搜索的起始位置// 防止重现重复的组合void backtracking(int n ,int k ,int startIndex){if(path.siz)e() == k){ret.push_back(path);// 收集结果return ;}// 如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){ // i为本次搜索的起始位置path.push_back(i);// 添加backtracking(n,k,i+1);// 纵向遍历path.pop_back();// 撤销}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return ret;}
};

• 模板题，在上一题的基础上，在收集结果的时候增加是否等于目标值的判断。

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(int k, int n,int startIndex){if(path.size() == k){// 满足指定和才收集if(accumulate(path.begin(),path.end(),0) == n)ret.push_back(path);return ;}for(int i = startIndex;i <= 9;i++){path.push_back(i);backtracking(k,n,i+1);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1);return ret;}
};

• 优化剪枝

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(int k, int n,int startIndex){if(path.size() == k){// 满足指定和才收集if(accumulate(path.begin(),path.end(),0) == n)ret.push_back(path);return ;}for(int i = startIndex;i <= 9-(k-path.size())+1;i++){// 剩余元素个数不足了，终止path.push_back(i);if(accumulate(path.begin(),path.end(),0) > n){// 已经大于目标值了，剪掉path.pop_back();return;}backtracking(k,n,i+1); path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k,n,1);return ret;}
};

• 注意题目的意思是，根据这几个数字所对应的字母进行组合。几个数字，每个组合就有几个元素。
• 从每个数字对应的元素中取一个。然后组合。
• 与上面题的不同，本体每一个数字代表的是不同的组合，也就是求不同集合之间的组合，而上面两道题，都是都同一个集合中的组合。

class Solution {
public:string path;vector<string>ret;const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};void backtracking(const string& digits,int index){if(index == digits.size()){// 每个数字对应的字母都取了一个，收集。ret.push_back(path);;return;}int digit = digits[index]-'0';//将对应char转为intstring letters = letterMap[digit];for(int i = 0; i< letters.size();i++){path.push_back(letters[i]);backtracking(digits,index+1);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size() == 0)return ret;backtracking(digits,0);return ret;}
};

• 隐藏回溯细节
  • 增加参数s,每次修改仅在调用递归函数传参时修改，递归结束返回回来，原值并未被修改。从而达到回溯效果。

class Solution {
public:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};vector<string>ret;void backtracking(const string& digits,string s,int index){// 增加参数stringif(index == digits.size()){ret.push_back(s);return  ;}int digit = digits[index]-'0';string leeters = letterMap[digit];for(int i =0; i < leeters.size();i++){backtracking(digits,s+leeters[i],index+1);// 回溯}}vector<string> letterCombinations(string digits) {if(digits.size() == 0)return ret;string s;s.clear();backtracking(digits,s,0);return ret;}
};

• 注意题目要求，所有元素不限制选取次数。在我们实际的代码中，要修改模板的控制下标。

>-  方法1: 需要排序，因为按顺序取，需要判断是否超出目标值，超过则终止当前层的选取——剪枝。
class Solution {
public:vector<vector<int>>ret;vector<int>path;void backtracking(vector<int>& candidates,int target,int startIndex){if(accumulate(path.begin(),path.end(),0) == target){ret.push_back(path);return ;}for(int i = startIndex; i < candidates.size();i++){path.push_back(candidates[i]);if(accumulate(path.begin(),path.end(),0) > target){// 在这里终止，因为是排序过了，后面的只会更大。所以终止选取。path.pop_back();return;}backtracking(candidates,target,i);// 不加1，重复当前值path.pop_back();}// 或者// for(int i = startIndex; i < candidates.size() && accumulate(path.begin(),path.end(),0) < target;i++){//     path.push_back(candidates[i]);//     backtracking(candidates,target,i);//     path.pop_back();// }}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());// 注意排序backtracking(candidates,target,0);return ret;}
};

• 方法2: 无序排序，递归后，收集结果前判断，是否超过目标，超过目标值终止计算，返回，继续选取下一个值。因为没排序，后面可能还有符合条件的。注意对比与方法1终止条件位置的不同。

class Solution {
public:vector<vector<int>>ret;vector<int>path;void backtracking(vector<int>& candidates,int target,int startIndex){if(accumulate(path.begin(),path.end(),0) > target){// 超过目标值则回退，不要再选啦。return ;}if(accumulate(path.begin(),path.end(),0) == target){ret.push_back(path);return ;}for(int i = startIndex; i < candidates.size();i++){path.push_back(candidates[i]);backtracking(candidates,target,i);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0);return ret;}
};

• 错误提示:
  • 参数startIndex，传递的时候不同于上面的两题，而是传入当前收集的值的下标，i，不是i+1,为了继续重复选取当前元素。
  • 开始我每次传的都是0，这样会造成重复的组合。

• 在上一题的基础上增加去重
• 去重1: 使用startIndex去重

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>& candidates,int target,int stratIndex){if(accumulate(path.begin(),path.end(),0) == target){ret.push_back(path);return  ;}for(int i = stratIndex;i < candidates.size();i++){// 去重if(i > stratIndex && candidates[i] == candidates[i-1])continue;path.push_back(candidates[i]);if(accumulate(path.begin(),path.end(),0) > target){path.pop_back();return;}backtracking(candidates,target,i+1);path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0);return ret;}
};

• 使用used数组去重——下面的90题子集II有更详细的去重解释。
  • 同一个树枝上的元素可以重复，同一个树层上的元素不可以重复。去的就是同一个树层的重。
  • 详见代码中的注释。

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>& candidates,int target,int stratIndex,vector<bool>&used){if(accumulate(path.begin(),path.end(),0) == target){ret.push_back(path);return  ;}for(int i = stratIndex;i < candidates.size();i++){// 去重，跳过同一层使用过的元素// used[i-1] == true,表明同一个树枝candiates[i-1]使用过——联想往下纵向遍历。// used[i-1] == false,表明同一个树层candiates[i-1]使用过——联想往右横向遍历。// 为什么？ used[i-1] == false;// 因为，同一树层，used[i-1] == false才能表示，当前取的candidates[i]是从candidates[i-1]回溯而来。// used[i-1] == true 说明进入下一层递归，向下纵向遍历，同一个树枝上使用过啦。// 与前一个元素与当前元素相等，并且在同一个树枝使用过，去掉。if(i > 0 && candidates[i] == candidates[i-1] &&used[i-1] == false)continue;path.push_back(candidates[i]);if(accumulate(path.begin(),path.end(),0) > target){path.pop_back();return;}used[i] = true;// 树枝使用了，遍历backtracking(candidates,target,i+1,used);used[i] = false;path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());vector<bool>used(candidates.size(),false);backtracking(candidates,target,0,used);return ret;}
};

• 可以说是回溯模板题，只是收集结果方式有所不同，判断从某一位置截取到当前位置的字串是否为回文字串， 是则收集。

class Solution {
public:// 判断是否为回文子串-双指针bool isPalindrome(const string& s,int start,int end){for(int i = start,j = end; i < j;i++,j--){if(s[i] != s[j])return false;}return true;}vector<vector<string>>ret;vector<string>path;void backtracking(const string& s, int startIndex){if(startIndex >= s.size()){// 收集一轮结果ret.push_back(path);return ;}for(int i = startIndex;i < s.size();i++){// 想象了一下搜索过程，每次递归刚进入先选一个字母，直到最后，然后开始返回，倒数第二次选两个，依次回溯调整选取状态...其中要判断每次选取的子串是否为回文子串。if(isPalindrome(s,startIndex,i)){// 是回文字串string str  = s.substr(startIndex,i-startIndex+1);path.push_back(str);// 收集}else continue;//不是回文字串backtracking(s,i+1);// 切割的地方不能重复切割，所以传入i+1path.pop_back();// 回溯}}vector<vector<string>> partition(string s) {backtracking(s,0);return ret;}
};

• 优化，提前计算出某一个子串是否是回文字串。dp思想。
• 具体来说, 给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串。

class Solution {
public:vector<vector<string>>ret;vector<string>path;vector<vector<bool>>isPalindrome;void backtracking(const string& s, int startIndex){if(startIndex >= s.size()){// 收集一轮结果ret.push_back(path);return ;}for(int i = startIndex;i < s.size();i++){if(isPalindrome[startIndex][i]){// 是回文字串string str  = s.substr(startIndex,i-startIndex+1);path.push_back(str);// 收集}else continue;//不是回文字串backtracking(s,i+1);path.pop_back();// 回溯}}// 计算每个子串是否为回文字串void computePalindrome(const string& s){isPalindrome.resize(s.size(),vector<bool>(s.size(),false));for(int i = s.size()-1;i >= 0;i--){for(int j = i;j < s.size();j++){if(j ==i)isPalindrome[i][j] = true;else if(j - i == 1)isPalindrome[i][j] = (s[i] == s[j]);else isPalindrome[i][j] = (s[i]==s[j] && isPalindrome[i+1][j-1]);}}}vector<vector<string>> partition(string s) {computePalindrome(s);backtracking(s,0);return ret;}
};

• 同上切割问题，可以使用回溯搜索法把所有可能性搜出来。

class Solution {
public:vector<string>ret;bool isValid(const string& s,int start,int end){if(start > end)return false;if(s[start] == '0' && start != end)return false;// 前导0，不合法int num = 0;for(int i = start;i <= end;i++){if(s[i] > '9' || s[i] < '0'){// 非数字return false;}// 从前往后遍历一个数转成整型num = num* 10 + (s[i]-'0');if(num >  255)return false;}return true;}void backtracking(string& s,int startIndex,int pointCount){if(pointCount == 3){if(isValid(s,startIndex,s.size()-1)){// 判断最后一段是不是合法的ret.push_back(s);// 在原字符串上修改}return ;}for(int i = startIndex;i < s.size();i++){if(isValid(s,startIndex,i)){// 判断这个区间子串是否合法s.insert(s.begin()+i+1,'.');// 在当前这个数字后面插入一个.pointCount++;backtracking(s,i+2,pointCount);// 注意，新加了一个点，所以要加2，到下一个数字pointCount--;s.erase(s.begin()+i+1);// 删除插入的点}else break;//不合法直接结束}}vector<string> restoreIpAddresses(string s) {if(s.size() < 4 || s.size() > 12)return ret;// 剪枝backtracking(s,0,0);return ret;}
};

• 方法1: 使用一个used数组来标记是否使用当前元素，0-暂时不考虑，1-使用，2-不使用。

class Solution {
public:vector<int>used;// 记录是否使用过vector<vector<int>>ret;void backtracking(vector<int>& nums,int startIndex){if(startIndex == nums.size()){// 到达边界出，开始收集结果vector<int>path;for(int i = 0; i <  nums.size();i++){if(used[i] == 1)path.push_back(nums[i]);}ret.push_back(path);return;}// startIndex当前位置used[startIndex] = 1;// 选当前位置backtracking(nums,startIndex+1);used[startIndex] = 0;// 恢复成未考虑状态used[startIndex] = 2;// 不选当前位置backtracking(nums,startIndex+1);used[startIndex] = 0;// 恢复成未考虑状态}vector<vector<int>> subsets(vector<int>& nums) {used.resize(nums.size(),0);backtracking(nums,0);return ret;}
};

• 方法2: 相对于方法2来说，方法1更直观一些。
  • 可结合下图理解，当前元素，选与不选的这个过程。
  • startIndex既是边界，也是当前要操作的元素。
  • 方法1，是通过使用used数组来标记当前元素(startIndex下标所对应的元素)选还是不选，最后到达边界，遍历原数组，统一收集结果path，在放入最终结果集ret中。
  • 方法2，则是将选的元素直接收集进path数组中，不选了，也就是回溯，再将其pop出来，此时不断移动边界startIndex直至到达边界。到达边界后，再将小数组path放进结果集ret中。

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>& nums,int startIndex){ret.push_back(path);// 收集结果if(startIndex == nums.size())return ;// 此终止条件可以省略for(int i = startIndex;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 ret;}
};

• 开始没想明白这跟上面那个题有什么区别，我说上面那个没说不让重复不也没重吗，其实不对，因为上面那个给的数据就不是重复的，所以求子集没重复，这题给的数据出现重复的元素了，所以就需要增加一个去重操作。
• 相当于40题组合总和II中，我们使用的used数组，是一个意思，但是我觉得那样的意思容易让人弄混，容易直译数组名used的含义，所以我们这里将其改为int型数组，1表示当前树枝上使用了，2表示当前树层上使用了，0表示暂未考虑。
  • 上方划线文字作废，就按照true表示当前树枝使用过，false表示当前树层使用过就行。
• 如下方图解所示，理解起来稍微有一点抽象，可以画图走一遍，下图仅给出第一次选1的分支。

• 仔细想一下，其实不难。
  • 就是先确定一点，即，这个树枝上第一个元素，我们称为"父亲",然后再往后选剩下的每一个数，即"孩子"
  • 重复的情况就是，当前这个元素上当前这个元素和前一个元素相同，并且前一个元素不是父亲元素(i > 0)，——说明，当前父亲和孩子的组合，出现过了，就是重复啦，去掉。
    • 那你可能就问了，那后面也是重复的吗，当然，再往后选孩子的孩子，也是重复的。因为在上一个"树枝"已经选取过了。
• 如下图所示意:

class Solution {
public:vector<int>path;vector<vector<int>>ret;vector<bool>used;void backtracking(vector<int>&nums,int startIndex){ret.push_back(path);// 注意本题收集结果的方式，每次递归都要收集结果。if(startIndex == nums.size())return;// 这行可以不加for(int i = startIndex;i < nums.size();i++){// i > 0防止越界if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)continue;// 去重path.push_back(nums[i]);used[i] = true;backtracking(nums,i+1);used[i] = false;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());// 排序，用于去重used.resize(nums.size(),false);backtracking(nums,0);return ret;}
};

• 方法2: 使用下标去重，看起来更简单些，但思想同使用used数组。此方法更贴切本题中第二张图。

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>&nums,int startIndex){ret.push_back(path);for(int i = startIndex;i < nums.size();i++){if(i > startIndex && nums[i] == nums[i-1])continue;// 去重path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());// 排序，用于去重backtracking(nums,0);return ret;}
};

• 方法3: 使用set去重,去重判断同理。不做过多解释。
  • 有趣的一点也是重要的一点是，注意，是先判断是出现过，然后在往set里emplace，这步就相当于使用used数组中的。可以对照理解一下。是一个意思。

if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)continue;// 去重

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>&nums,int startIndex){ret.push_back(path);unordered_set<int>set;for(int i = startIndex;i < nums.size();i++){if(set.find(nums[i]) != set.end())continue;// 去重path.push_back(nums[i]);set.emplace(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());// 排序，用于去重backtracking(nums,0);return ret;}
};

• 本题无法像上一题那样简单的使用used数组(bool数组)进行去重。
• 因为并不是简单的对比前一个元素，因为前一个元素不一定就可以放进去，也就是说如果(可以的话)仍使用上面used数组去重方式，逻辑会更加复杂。
• 方法1: 使用set去重，同上题使用set的方法，如下图所示，不理解就跟着走一下。

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>& nums,int startIndex){// 题目要求,递增要求，至少有两个元素if(path.size() > 1)ret.push_back(path);unordered_set<int>set;for(int i = startIndex;i < nums.size();i++){if(!path.empty() && nums[i] < path.back() ||set.find(nums[i]) != set.end())continue;set.emplace(nums[i]);path.push_back(nums[i]);backtracking(nums,i+1);// 为什么这里不用将set中的元素弹出来，因为我们每次递归进来都会创建一个set。是局部变量。详情见上图所示// 即每个set只负责本层。path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return  ret;}
};

• 方法2: 使用用数组模拟哈希表来去重

class Solution {
public:vector<int>path;vector<vector<int>>ret;void backtracking(vector<int>& nums,int startIndex){// 题目要求,递增要求，至少有两个元素if(path.size() > 1)ret.push_back(path);int used[201] = {0};// 数据范围-100到+100for(int i = startIndex;i < nums.size();i++){if(!path.empty() && nums[i] < path.back() ||used[nums[i]+100] == 1)continue;used[nums[i]+100] = 1;path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return  ret;}
};

• 相对于上面使用used数组去重，本题会更好理解些，我们使用used数组，仅仅来记录当前元素是否被使用过，而且不需要indexStart来记录每层递归开始的位置，而是每次都从头开始，从而收集所有的排列方式。
• 主要的一点是，不会给重复的数，以此为去重问题，见下题。

• 给上面的补充，写在这里，每一层，是指对应树枝的下面的每一层，不是整体的每一层。

class Solution {
public:vector<int>path;vector<vector<int>>ret;vector<bool>used;// 记录当前元素是否使用过，true使用过，false没使用过void backtracking(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return ;}for(int i = 0; i < nums.size() ;i++){if(used[i] == true)continue;// 该元素已经使用过啦path.push_back(nums[i]);used[i] = true;backtracking(nums);path.pop_back();used[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {used.resize(nums.size(),false);backtracking(nums);return ret;}
};

• 在上一题的基础上，给出重复的元素，需要增加去重。类似于上面求子集问题中的去重。
  • 在去重逻辑中，当前元素与前一位相等，并且前一位对应used为false,去掉。
  • 还是求子集问题中的去重道理。不过可以更简单的理解为，重复的数，以其为选中基准，重新排列组合出来的结果也是相同的(因为顺序固定了)。所以要去掉。——树层去重
  • 先选中的这个数为下面树层的根。

• 方法1: 树层去重

class Solution {
public:vector<int>path;vector<vector<int>>ret;vector<bool>used;// 用来记录是否使用过void backtracking(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return ;}for(int i = 0; i < nums.size();i++){if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)continue;if(used[i] == false){// 当前元素没使用，那就选上used[i] = true;// 使用path.push_back(nums[i]);backtracking(nums);// 递归used[i] = false;// 回溯path.pop_back();}}}vector<vector<int>> permuteUnique(vector<int>& nums) {used.resize(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums);return ret;}
};

• 方法2： 树枝去重
  • 即，对于树的每一个树枝来说，当我们确定了一个树层的根后，下面不可以再选与其相同的子根。

// 只需修改一步，将false改为true即可
// 如果理解了上面的我说的层的概念，这个树枝去重会很好理解。
if(i > 0 && nums[i] == nums[i-1] && used[i-1] == true)continue;

• 树层去重和树枝去重对比

• 可以很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位的去重虽然最后可以得到答案，但是做了很多无用搜索。

• 方法3: 使用set去重

class Solution {
public:vector<int>path;vector<vector<int>>ret;vector<bool>used;// 用来记录是否使用过void backtracking(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return ;}unordered_set<int>set;for(int i = 0; i < nums.size();i++){if(set.find(nums[i]) != set.end())continue;// 使用过了if(used[i] == false){// 当前元素没使用，那就选上used[i] = true;set.insert(nums[i]);path.push_back(nums[i]);backtracking(nums);used[i] = false;path.pop_back();}}}vector<vector<int>> permuteUnique(vector<int>& nums) {used.resize(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums);return ret;}
};

• 注意:
  • 使用set去重的版本相对于used数组的版本效率会低很多。
  • 因为频繁的对unordered_set进行insert操作，unordered_set需要做哈希映射(也就是把key通过hash function映射为唯一的哈希值)相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。

• 就是看能不能把所有票都用上。走完全程。

class Solution {
public:// 某一个机场可以到达的机场都有哪些，航班次数为这样的航班有几个。// 出发机场，<到达机场，航班次数>unordered_map<string,map<string,int>>targets;vector<string>ret;// 收集结果,沿途经过的机场数bool backtracking(int ticketNum){// ret.size()当前经过的机场数量 == 航班数量+1// 就是将所有票都用上了，终止。if(ret.size() == ticketNum + 1)return true;// 当前票都使用完毕//每次遍历的时候拿到上一个降落的机场，遍历这个机场接下来可以往哪飞for(pair<const string,int>& target : targets[ret[ret.size()-1]]){// 注意传引用，修改second值，const-因为map中的key不可修改。if(target.second > 0){// ret.push_back(target.first);target.second--;if(backtracking(ticketNum))return true;// 找到了终止，就不pop出来了ret.pop_back();// 回溯target.second++;}}return false;}vector<string> findItinerary(vector<vector<string>>& tickets) {targets.clear();for(const vector<string>& vec: tickets){// 记录映射关系-当前机场都能到哪个机场，能到达几次targets[vec[0]][vec[1]]++;// 计数，使用了当前票--，避免死循环。}ret.push_back("JFK");// 起始机场backtracking(tickets.size());return ret;}
};

• 时间复杂度: $O(n!)$
• 空间复杂度: $O(n)$,和子集问题同理
• 皇后们的要求
  • 不能同行
  • 不能同列
  • 不能同斜线,45 & 135

class Solution {
public:vector<vector<string>>ret;vector<string>chess_borad;void backtracking(int n,int row){// n为棋盘大小，row为当前到第几行if(row == n){// 每行都确定了皇后的位置ret.push_back(chess_borad);return ;}for(int col = 0; col < n;col++){if(isValid(row,col,n)){// 当前位置合法chess_borad[row][col] = 'Q';// 放置皇后backtracking(n,row+1);chess_borad[row][col] = '.';// 撤销皇后}}}// 判断当前位置放入皇后，是否合法bool isValid(int row,int col,int n){// 检查列for(int i = 0; i < row;i++){if(chess_borad[i][col] == 'Q')return false;}// 为什么这里没有单独检查行呢，因为递归的时候就是在调整行，递归一下，切换一下行。// 45度——也就是往右上判断，为什么不用判断左下判断，因为还没到下面的行。// 135度判断同理for(int i = row - 1,j = col + 1 ;i >=0 && j < n;i--,j++){if(chess_borad[i][j] == 'Q')return false;}for(int i = row - 1,j = col - 1; i >= 0 && j >= 0;i--,j--){if(chess_borad[i][j] == 'Q')return false;}return true;}vector<vector<string>> solveNQueens(int n) {chess_borad.resize(n,string(n,'.'));backtracking(n,0);return ret;}
};

• 时间复杂度: $O(9^m)$,m是’.'的数目
• 空间复杂度: $O(n^2)$,递归的深度是$O(n^2)$

• 判断棋盘是否合法
  • 同行是否重复
  • 同列是否重复
  • 9宫格里是否重复
• 就是一个萝卜一个坑，理论上来说有几个空白位置就会递归几层。递归只是为了找到坑位，不会再向后移动，搜寻别的坑。详见下方注释。

class Solution {
public:bool isValid(int row,int col,char val,vector<vector<char>> &board){for(int i = 0; i < 9;i++){// 检查同行是否有重复if(board[row][i] == val)return false;}for(int i = 0;i < 9;i++){// 检查同列是否有重复if(board[i][col] == val)return false;}// 检查九宫格内是否有重复int startRow = (row / 3)*3;//定位每个九宫格左上角位置int startCol = (col / 3)*3;for(int i = startRow;i < startRow + 3;i++){for(int j = startCol;j < startCol + 3;j++){if(board[i][j] == val)return false;}}return true;}bool backtracking(vector<vector<char>>& board){// 有趣的一点，我们发现在这里并没有控制下标访问，因为我们将某个空白位置放上了数字，board[i][j]就不为'.'啦，递归时就不会覆盖上一层所放的位置// 递归的时候会不断找到空的位置，尝试放入合法的数。也就是说每次层递归，都确定一个空位置被放入一个合法的数。// 就是一个萝卜一个坑，理论上来说有几个空白位置就会递归几层。递归只是为了找到坑位，不会再向后移动，搜寻别的坑。// 当某一层递归中，某一个空白放哪个数字都不行，return false,回溯，尝试将上一层所放置的位置换成别的，继续调整。for(int i = 0; i < 9;i++){for(int j = 0; j < 9;j++){if(board[i][j] == '.'){// 是空白for(char k = '1' ;k <= '9';k++){// 遍历，放置合适的数字if(isValid(i,j,k,board)){// 可以放board[i][j] = k;if(backtracking(board))return true;// 可以了就终止board[i][j] = '.';}}return false;// 九个数都是了，放哪个都不行，return false}}}return true;}void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};

• 这个回溯拖得时间还是比较长了，抓紧抓紧!Orz