回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

这里列出我接触的两个利用了典型的回溯思想解决的问题：

• 96. 不同的二叉搜索树II　　
• 22. 括号生成

个人简单总结

从这两个题中我个人感觉到的规律就是这类问题一般有 两种类型 ：

• 第一种相较于原问题是一个序列长度缩小的子问题，通过将一个根问题化解为若干个规模变小的子问题，便可以使用递归解决问题；
• 另一种一般对于每一个选项都可以选或者不选（或类似思路），一般会有 $O(2^n)$ 的时间复杂度。

在 递归函数中 需要注意的几点有：

1. 先定义判断结束的返回，即出口
2. 将问题化解为小问题（或是选或不选两个方向调用递归函数回溯）
3. 此时递归回溯阶段，之前的问题已经得到解决，在这里根据之前的结果加以处理返回

读者可以根据以上总结来阅读以下代码：

class Solution {
private: 
    vector<TreeNode*> generateTrees(int start, int end){
        //定义出口
        if(start>end){
            return {nullptr};
        }
        vector<TreeNode*> res;
        for(int i = start ;i<=end;i++){
            /****化解为小问题******/
            vector<TreeNode*> lefts = generateTrees(start,i-1);//递归
            vector<TreeNode*> rights = generateTrees(i+1,end);
            /*******************/

            //这里已经进入回溯阶段
            //利用结果分解当前问题
            for(auto left:lefts){
                for(auto right:rights){
                    TreeNode* node = new TreeNode(i, left, right);
                    res.push_back(node);
                }
            }
        }
        return res;
    }
public:
    vector<TreeNode*> generateTrees(int n) {
        //回溯法
        return generateTrees(1,n);  //问题所求
    }
};

接下来是学习笔记。

定义

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

白话：回溯法可以理解为通过选择不同的岔路口寻找目的地，一个岔路口一个岔路口的去尝试找到目的地。如果走错了路，继续返回来找到岔路口的另一条路，直到找到目的地。

典型问题

N皇后问题

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。（不能处在同一行，同一列，同一条斜线）

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

在实际撰写的过程中，发现思路并不难，但想要写出高效的题解不是一件非常轻松的事情。

1239. 串联字符串的最大长度

题目　　

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解 s 中最长长度。

 

示例 1：

输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
示例 2：

输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。
示例 3：

输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26  

提示：

• 1 <= arr.length <= 16
• 1 <= arr[i].length <= 26
• arr[i] 中只含有小写英文字母

思路：

这个题目就是上面所说两个类型中的第二个——对于每一个选项都可以选或者不选，这里专门贴出题目的范围：数组长度不超过16，每个句子长度不超过26，就是因为回溯对时间和空间的开销都很大，这里给出的数字并不大，所以我们可以考虑采用回溯的方法解决问题。
基本思路很简单，对于每个字符串，只有选择或者不选两种，时间复杂度为 $O(2^n)$ ，根据刚才总结的三步，定义出口，然后分选择和不选择分别递归，在这里由于是找到最大值，所以在判断出口的位置就可以完成比较，回溯部分没有任务。

class Solution {
    void bt(set<char>& set, int & maxR, int index, const vector<string>& arr, int inh){
        maxR = max(maxR, inh);
        int len = arr.size();
        if(index==len) return;
        int i = 0;
        std::set<char> single_set;   //单句子查重
        for(;i<arr[index].length();i++){
            if(set.find(arr[index][i])!=set.end() || single_set.find(arr[index][i])!=single_set.end()){
                //有一种情况是一个句子里有重复单词
                break;  //不能加
            }
            single_set.insert(arr[index][i]);
        }
        if(i==arr[index].length()){
            //能加，加        
            for(int i = 0;i<arr[index].length();i++){
                set.insert(arr[index][i]);
            }
            bt(set, maxR, index+1, arr, inh+arr[index].length());
            for(int i = 0;i<arr[index].length();i++){
                set.extract(arr[index][i]);
            }
        }
        bt(set, maxR, index+1, arr, inh);
    }
public:
    int maxLength(vector<string>& arr) {
        set<char> set;
        int maxR = 0;
        bt(set, maxR, 0, arr,0);
        return maxR;
    }
};

这里代码不太美观，下面给出官方题解简洁的题解。
主要思路是利用回溯 + 位运算，这里利用位运算排除重复字母是一个比较巧妙的思路。mask是作为形式参数传入，记录已经出现的字母位置，每个字符串有一个位数组记录，通过相与判断是否已经出现对应字母，通过相或来加入对应的字符串字母。

class Solution {
public:
    int maxLength(vector<string> &arr) {
        vector<int> masks;
        for (string &s : arr) {
            int mask = 0;
            for (char ch : s) {
                ch -= 'a';
                if ((mask >> ch) & 1) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
                    mask = 0;
                    break;
                }
                mask |= 1 << ch; // 将 ch 加入 mask 中
            }
            if (mask > 0) {
                masks.push_back(mask);
            }
        }

        int ans = 0;
        function<void(int, int)> backtrack = [&](int pos, int mask) {
            if (pos == masks.size()) {
                ans = max(ans, __builtin_popcount(mask));   // 数出所有字母数量
                return;
            }
            if ((mask & masks[pos]) == 0) { // mask 和 masks[pos] 无公共元素   加入字符串（选择的情况）
                backtrack(pos + 1, mask | masks[pos]);// 注意这里传入的是形参，mask没变，还是没有加入当前字符串的状态
            }
            backtrack(pos + 1, mask);   //（不选择）的情况
        };

        
        backtrack(0, 0);
        return ans;
    }
};