[数据结构与算法]回溯算法（一）

1. 回溯模板

for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这一棵树全遍历完了，?般来说，搜索叶?节点就是找的其中?个结果了。

2. 组合问题

2.1 LeetCode第17题—电话号码的字母组合

题解：

首先通过unordered_map构建一个映射，，此时有些像字符串的拼接，当选择到字符2的时候，它里面的字母有"def"，每一个都能够构成一种组合。

class Solution {
public:
    unordered_map<char,string> HashMap;
    //其实这道题仔细思考一下有点像是两层循环的味道
    //组合的长度应该和所提供的数字字符串长度一样
    void dfs(string digits,vector<string>& Allret,string Curstr,int index)
    {
        if(index == digits.size())
        {
            Allret.push_back(Curstr);
            return;//这个return是回退到了上一步的第二个字母不同的dfs中
        }
        //这一步相当于每次进行字符和字符串之间的转换，也就是需要我们所定义的unordered_map
        string curMap = HashMap[digits[index]];
        for(char ch : curMap)
        {
            //此时相当于拿到了第一个数字里面字符串所对应的字符
            dfs(digits,Allret,Curstr + ch,index+1);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> Allret;
        HashMap = {{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        if(digits.empty())
            return Allret;
        dfs(digits,Allret,"",0);
        return Allret;
    }
};

2.2 LeetCode第39题—组合总和

这里举例子进行一下说明：

题解：这里需要一个startindex，为的就是能够不出现重复的组合，对于解这类组合问题需要一个临时的数组和一个临时的sum总和，保存每个小过程中组合情况

class Solution {
public:
    //candidates可以无限取，只要能凑出来就行
    //如果两个组合当中数字都是一样的，那么这两个组合只能够看作一个，也就是题目所要求的的不能够有重复的，比如[2,2,3] [3,2,2]是一样的
    //这里的startindex就是要处理避免重复的组合，例如上面这个例子
    //可以一直的重复加自己的元素，直到符合target或者大于了target也就是不满足
    void dfs(vector<int>& candidates, int target,vector<vector<int>>& allRet,vector<int>& tmp,int Cursum,int startindex) 
    {
        if(Cursum > target)
            return;
        if(Cursum == target)
        {
            allRet.push_back(tmp);
            return;
        }
        for(int i = startindex;i<candidates.size();++i)
        {
            Cursum += candidates[i];
            tmp.push_back(candidates[i]);
            dfs(candidates,target,allRet,tmp,Cursum,i); //这里不需要i+1,表示可以重复的读取当前的数
            Cursum -= candidates[i];
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> allRet;
        if(candidates.empty())
            return allRet;
        vector<int> tmp;
        dfs(candidates,target,allRet,tmp,0,0);
        return allRet;
    }
};

3. 排列问题

3.1 全排列

链接：https://leetcode-cn.com/problems/permutations/

排列问题和组合问题的不同在于，排列是每次都需要从头检查一遍数组的，也就是说他不需要startindex这个。

class Solution {
public:
    void DFS(vector<int>& nums,vector<bool>& visited,vector<vector<int>>& ret,vector<int>& v)
    {
        if(v.size() == nums.size())
        {
            ret.push_back(v);
            return;
        }
        //排列问题时每次都要从头开始搜索的
        for(int i = 0;i<nums.size();++i)
        {
            if(visited[i] == true)
                continue;
            visited[i] = true;
            v.push_back(nums[i]);
            DFS(nums,visited,ret,v);
            v.pop_back();
            visited[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size(),false);
        vector<vector<int>> ret;
        vector<int> v;
        DFS(nums,visited,ret,v);
        return ret;
    }
};

3.2 字符串排列

链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
题解：对于字符串排序，组合这类题都是要使用拼接的思想的，一开始就是一个空字符串，然后不断的记录当前拼接的长度

class Solution {
public:
    void DFS(string& s,unordered_set<string>& us,vector<bool>& visited,string curstr,int k)
    {
        if(k == s.size())
        {
            us.insert(curstr);
            return;
        }
        for(int i = 0;i<s.size();++i)
        {
            if(visited[i] == false)
            {
                visited[i] = true;
                DFS(s,us,visited,curstr+s[i],k+1);
                visited[i] = false;
            }
        }
    }
    vector<string> permutation(string s) {
        unordered_set<string> us;
        vector<bool> visited(s.size(),false);
        DFS(s,us,visited,"",0);
        vector<string> v(us.begin(),us.end());
        return v;
    }
};

3.3 活字印刷

题解：对于这个图的解释其实在这段代码中还是不太一致的，因为他不管是否你字符串中是否有重复的，我都当做没有重复的在进行组合，那么如果出现了重复的，我只需要使用unordered_set进行一下去重即可

class Solution {
public:
    void DFS(string tiles,vector<bool>& visited,unordered_set<string>& us,string curstr)
    {
        if(!curstr.empty())
        {
            us.insert(curstr);
        }
        for(int i = 0;i<tiles.size();++i)
        {
            if(visited[i] == false)
            {
                visited[i] = true;
                DFS(tiles,visited,us,curstr+tiles[i]);
                visited[i] = false;
            }
        }
    }
    int numTilePossibilities(string tiles) {
        if(tiles.size() == 0)
            return 0;
        vector<bool> visited(tiles.size(),false);
        unordered_set<string> us;
        DFS(tiles,visited,us,"");
        return us.size();
    }
};

4. 棋盘问题

4.1 LeetCode第51题—N皇后I

题解：传过来的是当前行，然后判断在所有列中是否有合适的位置，如果有这个位置就可以保存起来

class Solution {
public:
    void DFS(vector<vector<pair<int,int>>>& allRet,vector<pair<int,int>>& curRet,int curRow,int n)
    {
        //走到这里说明已经是一个完整的N皇后结果了，可以进行保存了
        if(curRow == n)
        {
            allRet.push_back(curRet);
            return;
        }
        //这里是在判断这一行的每一列
        for(int i = 0;i<n;++i)
        {
            //这个Valid的作用是判断是否当前的这一行中的第i个位置没有和当前这一轮结果中皇后的位置造成冲突
            if(isValid(curRow,i,curRet))
            {
                curRet.push_back(make_pair(curRow,i));
                DFS(allRet,curRet,curRow+1,n);
                curRet.pop_back();
            }
        }
    }

    bool isValid(int row,int col,vector<pair<int,int>>& curRet)
    {
        //表示这个坐标是合法的，可以防止皇后的条件是：
        //首先不能同一行，也不能同一列，还不能同一上斜线，也不能下斜线
        //仔细分析就回发现，肯定在下一行选的坐标，所以不需要在判断是否为同一行，但是是否在同一列还是需要进行判断的
        //其次就是如果是同一上斜线的，你会发现他们的坐标值相加是一样的
        //如果是同一下斜线，那么他们的坐标值相减是一样的
        for(pair<int,int>& e : curRet)
        {
            if(col == e.second || e.first + e.second == row + col || e.first - e.second == row - col)
                return false;
        }
        return true;
    }
    //这个函数就是一个把坐标值转换为所需的字符串形式的类型
    vector<vector<string>> transtr(vector<vector<pair<int,int>>>& allRet,int n)
    {
        vector<vector<string>> ret;
        //这一步相当于拿到了一个vector,里面存的都是当前这个方案中皇后存放的位置坐标
        for(vector<pair<int,int>>& e : allRet)
        {
            vector<string> v(n,string(n,'.'));
            for(pair<int,int>& i : e)
            {
                v[i.first][i.second] = 'Q';
            }
            ret.push_back(v);
        }
        return ret;
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<pair<int,int>>> allRet;
        vector<pair<int,int>> curRet; //此时这里面存放的是当前的皇后坐标情况
        DFS(allRet,curRet,0,n);
        return transtr(allRet,n);
    }
};

4.2 N皇后II

链接：https://leetcode-cn.com/problems/n-queens-ii/

题解：判断方案的个数反而更简单一下了。

class Solution {
public:
    void DFS(vector<vector<pair<int,int>>>& allRet,vector<pair<int,int>>& curRet,int curRow,int n)
    {
        //走到这里说明已经是一个完整的N皇后结果了，可以进行保存了
        if(curRow == n)
        {
            allRet.push_back(curRet);
            return;
        }
        //这里是在判断这一行的每一列
        for(int i = 0;i<n;++i)
        {
            //这个Valid的作用是判断是否当前的这一行中的第i个位置没有和当前这一轮结果中皇后的位置造成冲突
            if(isValid(curRow,i,curRet))
            {
                curRet.push_back(make_pair(curRow,i));
                DFS(allRet,curRet,curRow+1,n);
                curRet.pop_back();
            }
        }
    }

    bool isValid(int row,int col,vector<pair<int,int>>& curRet)
    {
        //表示这个坐标是合法的，可以防止皇后的条件是：
        //首先不能同一行，也不能同一列，还不能同一上斜线，也不能下斜线
        //仔细分析就回发现，肯定在下一行选的坐标，所以不需要在判断是否为同一行，但是是否在同一列还是需要进行判断的
        //其次就是如果是同一上斜线的，你会发现他们的坐标值相加是一样的
        //如果是同一下斜线，那么他们的坐标值相减是一样的
        for(pair<int,int>& e : curRet)
        {
            if(col == e.second || e.first + e.second == row + col || e.first - e.second == row - col)
                return false;
        }
        return true;
    }
    int totalNQueens(int n) {
        vector<vector<pair<int,int>>> allRet;
        vector<pair<int,int>> curRet; //此时这里面存放的是当前的皇后坐标情况
        DFS(allRet,curRet,0,n);
        return allRet.size();
    }
};

5. 普通回溯法

5.1 剑指offer12题—矩阵中的路径

链接: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

class Solution {
public:
    //这道题的标准解法是回溯法，做到这里也就说明了回溯法还是做得有问题，需要继续好好学习
    bool DFS(int i,int j,int row,int col,vector<vector<char>>& board, string word,vector<vector<int>>& visited,int k)
    {
        if(i < 0 || i >= row || j <0 || j >= col || board[i][j] != word[k] || visited[i][j] == 1)
            return false;
        //此时说明字符串已经完全匹配上了
        if(k == word.size()-1)
            return true;
        visited[i][j] = 1; //表示这个位置已经被访问过了
        //只需要任意一个满足即可，但是如果此时又多个位置都满足，但是第一个位置递归进去，后面发现是不合适的，所以此时需要一个返回值，所以后面才需要ret
        bool ret = DFS(i+1,j,row,col,board,word,visited,k+1) || DFS(i,j+1,row,col,board,word,visited,k+1) ||
        DFS(i-1,j,row,col,board,word,visited,k+1) || DFS(i,j-1,row,col,board,word,visited,k+1);
        //对于回溯一定要有回退的这一步
        visited[i][j] = 0;
        return ret;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int row = board.size();
        int col = board[0].size();
        vector<vector<int>> visited(row,vector<int>(col,0));
        for(int i = 0;i<row;++i)
        {
            for(int j = 0;j<col;++j)
            {
                if(board[i][j] == word[0])
                {
                    //以第一个字符当做进入DFS的条件
                    if(DFS(i,j,row,col,board,word,visited,0))
                        return  true;
                }
            }
        }
        return false;
    }
};

5.2 剑指offer34题—二叉树和为某一值的路径

链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

题解：这道题的解法其实是类似于二叉树的前序遍历的递归写法的，只是在这个前序遍历的过程中增加了几个判断条件。

class Solution {
public:
    //回溯法可以解决这个问题
    void DFS(TreeNode* root,int target,vector<vector<int>>& vv,vector<int>& v)
    {
        if(root == nullptr)
            return;
        v.push_back(root->val);
        target -= root->val;
        //也就是题目中所说的叶子结点的条件
        if(root->left == nullptr && root->right == nullptr && target == 0)
        {
            //说明此时这个就是我要找的路径
            vv.push_back(v);
        }
        DFS(root->left,target,vv,v);
        DFS(root->right,target,vv,v);
        //如果走到这里，所以当前的这个结点适不适合的，不满足条件的，所以应该回溯
        v.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<vector<int>> vv;
        vector<int> v;
        DFS(root,target,vv,v);
        return vv;
    }
};