回溯算法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

1.回溯法的效率

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

2.回溯法解决的问题

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

3.如何理解回溯法

回溯法解决的问题都可以抽象为树形结构

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

4.回溯法模板

1.回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

void backtracking(参数)

2.回溯函数终止条件

既然是树形结构，就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

3.回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。backtracking这里自己调用自己，实现递归。

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

分析完过程，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

5.组合问题：

组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
判断结束的方法：一般结果集满足条件结束

77. 组合

题目难度：中等用时： 15 分钟标记：完成

class Solution {
    vector<vector<int>>res;
    vector<int> now;
    void searchk(int start ,int n, int k)
    {
        if (now.size() == k)
        {
            res.push_back(now);
            return;
        }
        for (int i = start; i <= n; ++i) {
            now.push_back(i);
            searchk(i+1 ,n,k); //注意这里，如果写成searchk(i ,n,k); 就是可以取重复元素（当前），i取0就是排列问题
            now.pop_back();
        }

    }
public:
    vector<vector<int>> combine(int n, int k) {
        
        searchk(1 , n, k);
        return res;
    }
};

216. 组合总和 III

题目难度：中等用时： 10 分钟标记：完成

class Solution {
    vector<vector<int>>res;
    vector<int>now;
    void backtracking(int k ,int n ,int start)
    {
        if (now.size() == k)
        {
            if (n == 0)res.push_back(now);
            return;
        }
        for (int i = start; i <=9 && i <= n; ++i) {
            now.push_back(i);
            n-=i;
            backtracking( k , n , i+1);
            now.pop_back();
            n+=i;
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking( k , n , 1);
        return res;
    }
};

17. 电话号码的字母组合

题目难度：中等用时： 12 分钟标记：完成

class Solution {
    vector<string> res;
    string now;
    vector<string> process;
    void backtracking(int start)
    {
        if (now.size() == process.size())
        {
            res.push_back(now);
            return;
        }
        for (int i = start; i < process.size(); ++i) {
            for (int j = 0; j < process[i].size(); ++j) {
                now+=process[i][j];
                backtracking(i+1);
                now.pop_back();
            }
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits == "") return {};
        vector<string> numap{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        for (int i = 0; i < digits.size(); ++i) {
            process.push_back(numap[digits[i] - '0']);
        }
        backtracking(0);
        return res;

    }
};

39. 组合总和

题目难度：中等用时： 7 分钟标记：完成

class Solution {
    vector<vector<int>> res;
    vector<int> now;
    void backtracking(vector<int>& candidates, int target,int start)
    {
        if (target <= 0)
        {
            if (target == 0) res.push_back(now);
            return;
        }
        for (int i = start; i < candidates.size()  ; ++i) {
            now.push_back(candidates[i]);
            target-=candidates[i];
            backtracking(candidates,  target, i); //等于i时候可以取重复元素
            now.pop_back();
            target+=candidates[i];
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,  target, 0);
        return res;
    }
};

40. 组合总和 II

去重问题

题目难度：中等用时： 14 分钟标记：未完成

注意要点：

数层上的去重操作

1.需要对原始数组进行排序

2.初始化一个used数组，对树层去重

3.如果for循环到此上一个used[i-1]为false，并且这个元素等于上一个元素，则这个就是重复

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

class Solution {
    vector<vector<int>> res;
    vector<int> now;
    vector<bool> used;//初始化一个used数组，对树层去重
    void backtracking(vector<int>& candidates, int target,int start)
    {
        if (target <= 0)
        {
            if (target == 0) res.push_back(now);
            return;
        }
        for (int i = start; i < candidates.size()  ; ++i) {
            //3.如果for循环到此上一个used[i-1]为false，并且这个元素等于上一个元素，则这个就是重复
            //为什么used[i-1] == false，因为等于true是属于树根，这个不需要去重，数层上这个节点为false
            if (i>0 && used[i-1] == false && candidates[i] == candidates[i-1]) continue;
            used[i] = true;
            now.push_back(candidates[i]);
            target-=candidates[i];
            backtracking(candidates,  target, i+1);
            now.pop_back();
            target+=candidates[i];
            used[i] = false;
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        std::sort(candidates.begin(), candidates.end()); //1.需要对原始数组进行排序
        used.assign(candidates.size(), false);
        backtracking(candidates,  target, 0);
        return res;
    }
};

6.切割问题：

131. 分割回文串

切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。
判断结束的方法：一般start == num.size()结束

题目难度：中等用时： 14 分钟标记：未完成

在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

class Solution {
    vector<vector<string>> res;
    vector<string> now;
    bool huiwen(string &s)
    {
        string p(s);
        std::reverse(p.begin(), p.end());
        return p == s;
    }
    void backtracking(string &s,int start)
    {
        if (start >= s.size())
        {
            res.push_back(now);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            string sub = s.substr(start,i+1-start); //[startIndex, i]
            if (huiwen(sub))
            {
                now.push_back(sub);
                backtracking(s, i + 1);
                now.pop_back();
            }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return res;
    }
};

93. 复原 IP 地址

题目难度：中等用时： 16 分钟标记：完成

//93. 复原 IP 地址
class Solution {
public:
    vector<string> res;
    bool isV(string s)
    {
        if (s.size() > 1 && s[0] == '0') return false;
        if (stoi(s) > 255) return false;
        return true;
    }
    void getIP(string s,int startIndex,string now,int count)
    {
        if (count>4) return;
        if(startIndex>= s.size() && count == 4)
        {
            now.pop_back();
            res.push_back(now);
            return;
        }

        for (int i = startIndex; i < s.size() && i-startIndex < 3; ++i) {
            string sub = s.substr(startIndex,i-startIndex+1);
            if (isV(sub))
            {
                getIP( s, i+1,now+sub+".",count+1);
            } 

        }
    }
    vector<string> restoreIpAddresses(string s) {
        getIP( s, 0,"",0);
        return res;

    }
};

7.子集问题

78. 子集

题目难度：中等用时： 5 分钟标记：完成

因为是遍历所有结果，所有所有情况都要收集

//78. 子集
//方法一：二进制搜索法
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {

        int n = 0;
        vector<vector<int>> result;
        while (n < pow(2,nums.size()))
        {
            int temp = n;
            vector<int> vvector;
            for (int i = 0; i < nums.size(); ++i) {
                if (temp % 2)
                {
                    vvector.push_back(nums[i]);
                }
                temp = temp / 2;
            }
            result.push_back(vvector);
            n++;
        }
        return result;

    }
};

//方法二：回溯法
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己，每个节点都取值
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

90. 子集 II

题目难度：中等用时： 12 分钟标记：完成

class Solution {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used; //定义是否用过
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己，每个节点都取值
        for (int i = startIndex; i < nums.size(); i++) {
            if (i > 0 && nums[i-1]==nums[i] && used[i-1] == false) continue;//数层去重
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        used.assign(nums.size(), false);
        backtracking(nums, 0);
        return result;
    }
};

491. 递增子序列

题目难度：中等用时： 24 分钟标记：未完成

class Solution {
    vector<vector<int>>res;
    vector<int> now;
    
    void backtracking(vector<int>& nums,int start)
    {
        if (now.size() > 1)   res.push_back(now);
        unordered_set<int> uset; //本层用map来做
        for (int i = start; i < nums.size(); ++i) {
            if (now.size() > 0 && now.back() > nums[i] ||  uset.find(nums[i]) != uset.end()) continue;//收集的最后一个元素不满足递增，这里注意是|| 或者
            uset.insert(nums[i]);//
            now.push_back(nums[i]);
            backtracking(nums, i + 1);
            now.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking( nums, 0);
        return res;
    }
};

8.排列问题

46. 全排列

题目难度：中等用时： 12分钟标记：完成

class Solution {
    vector<vector<int>>res;
    vector<int>now;
    vector<bool>used;
    void backtraking(vector<int>& nums)
    {
        if (now.size() == nums.size())
        {
            res.push_back(now);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i])continue;
            used[i] = true;
            now.push_back(nums[i]);
            backtraking( nums);
            now.pop_back();
            used[i] = false;
        }

    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.assign(nums.size(), false);
        backtraking(nums);
        return res;
    }
};

47. 全排列 II

题目难度：中等用时： 8分钟标记：完成

class Solution {
    vector<vector<int>>res;
    vector<int>now;
    vector<bool>used;
    void backtraking(vector<int>& nums)
    {
        if (now.size() == nums.size())
        {
            res.push_back(now);
            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])continue;
            used[i] = true;
            now.push_back(nums[i]);
            backtraking( nums);
            now.pop_back();
            used[i] = false;
        }

    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        used.assign(nums.size(), false);
        backtraking(nums);
        return res;
    }
};

9.棋盘问题

51. N 皇后

题目难度：困难用时： 30分钟标记：未完成

//51. N 皇后
class Solution {
public:
    vector<vector<string>> res;
    //此函数用来判断是否合法加入Q
    bool isvalid(const vector<string> &now,int row,int col)
    {
        for (int i = 0; i < now.size(); ++i) {
            if (now[i][col]=='Q') return false;
        }
        int i = row+1;
        int j = col+1;
        while (i!=now.size() && j!=now.size() )
        {
            if (now[i][j]=='Q') return false;
            i++;
            j++;
        }
        i = row-1;
        j = col-1;
        while (i>=0 && j>=0 )
        {
            if (now[i][j]=='Q') return false;
            i--;
            j--;
        }

        i = row-1;
        j = col+1;
        while (i>=0 && j!=now.size() )
        {
            if (now[i][j]=='Q') return false;
            i--;
            j++;
        }
        i = row+1;
        j = col-1;
        while (i!=now.size() && j>=0 )
        {
            if (now[i][j]=='Q') return false;
            i++;
            j--;
        }
        return true;

    }

    void getresult(vector<string> &now,int n , int row) //注意点1：row为参数，表示运行到了几行，每一行就是深搜
    {
        if (n == row)
        {
            res.push_back(now);
            return;
        }
        //注意点2：for是广搜，搜索每一列，所以要从0开始搜索 i = 0，当前行为row，列为i
        for (int i = 0; i < n; ++i) {
            if (isvalid(now, row, i))
            {
                now[row][i] = 'Q';//这里回溯
                getresult(now,n,row+1);//这里下一行的参数，传入的是row + 1，而不是列的i + 1
                now[row][i] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        string i(n,'.');
        vector<string> now(n,i);
        getresult(now,n,0);
        return res;
    }
};

52. N 皇后 II

题目难度：困难用时： 30分钟标记：完成

//52. N 皇后 II
class Solution {
public:
    //vector<vector<string>> res;
    int count = 0;
    bool isvalid(const vector<string> &now,int row,int col)
    {
        for (int i = 0; i < now.size(); ++i) {
            if (now[i][col]=='Q') return false;
        }
        int i = row+1;
        int j = col+1;
        while (i!=now.size() && j!=now.size() )
        {
            if (now[i][j]=='Q') return false;
            i++;
            j++;
        }
        i = row-1;
        j = col-1;
        while (i>=0 && j>=0 )
        {
            if (now[i][j]=='Q') return false;
            i--;
            j--;
        }

        i = row-1;
        j = col+1;
        while (i>=0 && j!=now.size() )
        {
            if (now[i][j]=='Q') return false;
            i--;
            j++;
        }
        i = row+1;
        j = col-1;
        while (i!=now.size() && j>=0 )
        {
            if (now[i][j]=='Q') return false;
            i++;
            j--;
        }
        return true;

    }

    void getresult(vector<string> &now,int n , int row)
    {
        if (n == row)
        {
            count++;
            return;
        }

        for (int i = 0; i < n; ++i) {
            if (isvalid(now, row, i))
            {
                now[row][i] = 'Q';
                getresult(now,n,row+1);
                now[row][i] = '.';
            }
        }
    }
    int totalNQueens(int n) {
        string i(n,'.');
        vector<string> now(n,i);
        getresult(now,n,0);
        return count;
    }
};

37. 解数独

题目难度：困难用时： 30分钟标记：未完成

//37. 解数独
class Solution {
public:
    //注意点1：isValid 判断函数
    bool isValid(vector<vector<char>>& board,int row,int col,char num)
    {
        for (int i = 0; i < board.size(); ++i) {
            if(board[i][col]==num || board[row][i]==num)return false;
        }
        int i = (row/3 ) *3;
        int j = (col/3 ) *3;
        for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
                if (board[i+k][j+l] == num ) return false;
            }
        }
        return true;
    }
    bool find(vector<vector<char>>& board)
    {
        //注意点2：两层回溯，需要返回值，从而判断找没找到
        for (int col = 0; col < 9; ++col) {
            for (int row = 0; row < 9; ++row) {
                if (board[row][col]=='.')
                {
                    for (char i = '1'; i <='9' ; ++i) {
                        if(isValid(board, row, col,i))
                        {
                            board[row][col] = i;
                            bool f = find( board);
                            if (f) return true;//注意点3：找打了需要return ,不必搜索
                            board[row][col] = '.';
                        }
                    }
                    return false;//注意点4：找不到需要return false
                }
            }

        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        find( board);
    }
};

79. 单词搜索(未)

class Solution {
    bool find = false;
    vector<vector<bool>> vis;
    void  backtracking(vector<vector<char>>& board,string &word ,int raw ,int col ,int st)
    {
        if (raw < 0 || col < 0 || raw >= board.size() || col >= board[0].size() || board[raw][col] != word[st] || find || vis[raw][col]) return;
        if (st == word.size() -1)
        {
            find = true;
            return;
        }
        vis[raw][col] = true;
        backtracking( board,word ,raw+1 ,col ,st+1);
        backtracking( board,word ,raw ,col+1 ,st+1);
        backtracking( board,word ,raw ,col-1 ,st+1);
        backtracking( board,word ,raw-1 ,col ,st+1);
        vis[raw][col] = false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        find = false;
        vis.assign(board.size(),vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (board[i][j] == word[0]) backtracking(board,word,i,j,0);
            }
        }
        return find;
    }
};

回溯算法

1.回溯法的效率​

2.回溯法解决的问题​

3.如何理解回溯法​

4.回溯法模板​

5.组合问题：​

去重问题​

6.切割问题：​

7.子集问题​

8.排列问题​

9.棋盘问题​

79. 单词搜索(未)​