算法基础-----【递归回溯】

1、递归

递归是一种算法结构，递归会出现在子程序中自己调用自己或间接地自己调用自己。递归就是分为递去和归来。

递去：递归的问题必须可以分解为若干规模较小，与原问题相同的子问题，这些子问题可以用相同的解题思路解决。

归来：这些问题的演化过程是一个从小到大、由远及近的过程，并且会有一个明确的终点，一旦到了这个明确的终点后，就需要从原路返回到原点了(类比迷宫的分叉点)，原问题就能解决了。

数学归纳法三个关键要素：

1）步进表达式：问题蜕变成子问题的表达式
2）结束条件：什么时候可以不再使用步进表达式
3）直接求解表达式：在结束条件下能够直接计算返回值的表达式

模板一：在递去中解决问题（回溯法模板）

  function recursion(大规模){
  if(end_condition){		//找到一个可行解，返回
  	end;			//给出到达递归边界需要进行的处理
  }
  else{				//在将问题转换为子问题的每一步，解决该步中剩余部分的问题
  	solve;			//解决该步中的剩余问题，递去
  	recursion(小规模);	//转换为下一个子问题，递到最深处不断归来
  }
}

模板二：在归来的过程中解决问题（分治法模板）

  function recursion(大规模){
  if(end_condition){		//找到一个可行解，返回
  	end;			//给出到达递归边界需要进行的处理
  }
  else{				//在将问题转换为子问题的每一步，解决该步中剩余部分的问题
  	recursion();		//递去
  	slove;	//递到最深处，不断归来
  }
}

2、回溯算法（DFS暴力）

回溯是一种算法思想，可以用递归实现。回溯是递归的副产品，只要有递归就会有回溯。（回溯函数=递归函数）。回溯的本质就是穷举，穷举所有可能，然后选择我们想要的答案。果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。回溯解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

2.1回溯法解决的问题：

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

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

组合是不强调元素顺序的，排列是强调元素顺序。{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序。而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。

2.2回溯三部曲

递归三部曲（树）

回溯三部曲：

1.回溯函数模板返回值以及参数（void backtracking(参数)）

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

2.回溯函数终止条件

一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

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

3.回溯搜索的遍历过程

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

在这里插入图片描述

void backtracking(参数)
    if(终止条件){
        存放结果；
        return;
    }
	for(选择：本层集合中的元素（树中节点孩子的数量就是集合大小）){
        处理节点；
        backtracking(路径，选择列表);
        回溯，撤消处理结果
    }

回溯算法题解

1、组合问题

【77】组合问题

class Solution {
private:
    vector<vector<int>> res;//存放最终的结果
    vector<int> path;//存放一次递归的结果
    //n,k,每次开始的index
    void backtracking(int n,int k,int startindex){
        //1.回溯终止条件
        if(path.size() == k){
            res.push_back(path);
            return;
        }

        //2.本层元素 单层递归
        for(int i =startindex;i<=n;i++){
            //处理节点
            path.push_back(i);
            //递归
            backtracking(n,k,i+1);
            //回溯
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtracking(n,k,1);
        return res;
    }
};

【216】组合总和Ⅲ

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k,n,1);
        return res;
    }
private:
    void backtracking(int k,int n,int startindex){
        if(sum > n)return;//减枝
        if(path.size() == k){
            if(sum == n) res.push_back(path);
            return;
        }

        for(int i = startindex;i<=9;i++){
            sum+=i;
            path.push_back(i);
            backtracking(k, n,i+1);
            sum-=i;
            path.pop_back();
        }
        
    }
    int sum =0;
    vector<vector<int>> res;
    vector<int> path;
};

【17】电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution {

public:
    vector<string> letterCombinations(string digits) {
        //边界判定
        if(digits.size() == 0)return res;
        backtracking(digits,0);
        return res;
    }
private:
    void backtracking(string digits,int index){
        if(index == digits.size()){
            res.push_back(path);
            return;
        }
        //索引数组
        int digit  = digits[index] -'0';//转为int
        //当层遍历
        string letter = mp[digit];
        for(int i =0;i<letter.size();i++){
                auto iter = mp.find(digit);
                path.push_back(iter->second[i]);
                backtracking(digits,i+1);//index+1
                path.pop_back();
        }
    }
    unordered_map<int,string> mp = {
        {0,""},{1,""},{2,"abc"},
        {3,"def"},{4,"ghi"},{5,"jkl"},
        {6,"mno"},{7,"pqrs"},{8,"tuv"},{9,"wxyz"}
    };
    vector<string> res;
    string path;
};

【39】组合总和

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if(candidates.size() == 0)return res;
        path.clear();
        res.clear();
        backtracking(candidates,target,0);
        return res;
    }

private:
    void backtracking(vector<int>& candidates, int target,int index){
        if(sum == target){
            res.push_back(path);//sum不需要等于0，直接吐出来回溯其他的
            return;
        }
        if(sum>target||res.size()>150){//递归结束
            return;
        }

        for(int i =index;i<candidates.size();i++){//本层
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,i);//回溯 注意传入i,可以重复传入
            sum-=candidates[i];
            path.pop_back();//这里没对
        }
            
    }
    int sum =0;
    vector<int> path;//存放路径
    vector<vector<int>> res;//存放path
};

【40】组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

集合（数组candidates）有重复元素，但还不能有重复的组合。去重：不同组合不能有重复的元素，也就是说去重的是同一层树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
强调一下，树层去重的话，需要对数组排序！
在这里插入图片描述

先给数组排序，然后要加if条件排除同层相同的元素

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        res.clear();
        sort(candidates.begin(),candidates.end());//排序
        backtracking(candidates,target,0);
        return res;
    }
private:
    void backtracking(vector<int>& nums,int target,int startindex){
        if(sum>target){
            return;
        }
        if(sum ==target ){
            res.push_back(path);
        }
        
        for(int i = startindex;i<nums.size();i++){
            if(i > startindex &&nums[i-1] == nums[i]){//从第二次开始，不能有重复的 写反的逻辑
                continue;
            }else{
                sum+=nums[i];
                path.push_back(nums[i]);
                backtracking(nums,target,i+1);//每个数只能用一次
                sum-=nums[i];
                path.pop_back();
            }

        }
    }
    vector<vector<int>> res;
    vector<int> path;
    int sum;
};

切割问题

【131】分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return res;
    }
private:
    void backtracking(string s,int startindex){
        if(startindex >= s.size()){//终止条件
            res.push_back(path);
            return;
        }
        //单层回溯
        for(int i =startindex;i<s.size();i++){
            if(isParo(s,startindex, i)){//判断是否是回文数组
                string str = s.substr(startindex, i - startindex + 1);
                 path.push_back(str);
            }else{
                continue;
            }
            backtracking(s,i+1);
            path.pop_back();
        }

       

    }
    //判断是否是回文串 变式，加入了start和end
    bool isParo(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>> res;
    vector<string> path;

};

【 93】复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        res.clear();
        if(s.size()>12||s.size()<4)return res;
        backtracking(s,0);
        return res;
    }
private:
    void backtracking(string &s,int startindex){
        //到终点
        if(pointcount == 3){
            if(isValid(s,startindex,s.size()-1)){//判断第四段的数字是不是合法的
                res.push_back(s); 
            }
            return;
        }

        //本层遍历
        int i;
        for( i =startindex;i< s.size();i++){
            if(isValid(s,startindex,i)){
                s.insert(s.begin()+i+1, '.');
                pointcount++;
                backtracking(s,i+2);
                s.erase(s.begin()+i+1);
                pointcount--;
            }else{
                break;
            }
        }
    }

    bool isValid(string &s,int startindex,int endindex){
        if(startindex>endindex)return false;
        if(s[startindex] == '0'&&startindex!=endindex)return false;
        string str = s.substr(startindex,endindex-startindex+1);
        int num = stoi(str);
        if(num <=255){
            return true;
        }
        return false;
    }
    vector<string> res;
    int pointcount;
};

子集问题

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的
子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和子集{2,1}是一样的。那么既然是无序，**取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！**有同学问了，什么时候for可以从0开始呢？
求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。

【78】子集

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        res.clear();
        path.clear();
        recurse(nums,0);
        return res;
    }
private:
    void recurse(vector<int>& nums,int startindex){
        res.push_back(path);//要放在上面，收集每个点
        if(startindex >=nums.size()){//没有剩余元素了 这里收集的是叶子节点
            
            return;
        }

        for(int i =startindex;i<nums.size();i++){
            path.push_back(nums[i]);
            recurse(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> res;
    vector<int> path;
};

这道题目和78.子集 (opens new window)区别就是集合里有重复元素了，而且求取的子集要去重。

【90】子集II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.clear();
        path.clear();
        sort(nums.begin(),nums.end());
        backtracking(nums,0);
        return res;
    }
private:
    void backtracking(vector<int>& nums,int startindex){
        res.push_back(path);
        if(startindex > nums.size()){
            return;
        }
        for(int i =startindex;i<nums.size();i++){
            if(i >startindex && nums[i] == nums[i-1]){//重复的情况
                continue;
            }else{
                path.push_back(nums[i]);
                backtracking(nums,i+1);
                path.pop_back();
            }

        }
    }
    vector<vector<int>> res;
    vector<int> path;
};

排列问题

【46】全排列

全排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

重点是存一个used数组标记哪些元素是用过的
在这里插入图片描述

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        path.clear();
        res.clear();
        vector<int> used(nums.size());
        backtracking(nums,used);
        return res;
    }
private:
    void backtracking(vector<int>& nums,vector<int>& used){
        if(path.size() == nums.size()){//到叶子结点结束
            res.push_back(path);
            return;
        }

        for(int i = 0;i<nums.size();i++){//需要从0开始，因为每个元素都要遍历到
            if(used[i] != 1){
                used[i] = 1;
                path.push_back(nums[i]);
                backtracking(nums,used);
                used[i] = 0;
                path.pop_back();
            }else{
                continue;
            }

        }
    }
    vector<vector<int>> res;
    vector<int> path;
};

【47】全排列II

给定的是重复的数组，给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

要包含不重复，就要用used数组去比较

【22】括号生成

全排列没有剪枝的情况。


class Solution {
public:
    vector<string> generateParenthesis(int n) {
        res.clear();
        path.clear();
        string str = "()";
        backtrack(str, n);
        return res;
    }

private:
    void backtrack(string const &str, int n) {
        if (path.size() == n * 2) {
            if (isValid(path)) {
                res.push_back(path);
            }
            return;//都要return
        }
        for (int i = 0; i < 2; i++) {
            path.push_back(str[i]);
            backtrack(str, n);
            path.pop_back();
        }
    }

    bool isValid(string &path) {
        stack<char> stk;
        for (char ele : path) {
            if (ele == '(') {
                stk.push(ele);
            } else {
                if (stk.empty()) {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }

    vector<string> res;
    string path;
};

然后发现剪枝一下更快，右括号没有最好

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        res.clear();
        path.clear();
        string str = "()";
        backtrack(n,0,0);
        return res;
    }

private:
    void backtrack(int n,int open,int close) {
        if (path.size() == n * 2) {
            if (isValid(path)) {
                res.push_back(path);
            }
            return;//都要return
        }
		
        //不用for，直接分两种情况讨论，但是要统计括号的多少
        if(open < n){
            path.push_back('(');
            backtrack(n,open+1,close);
            path.pop_back();
        }
        if (close < open) {
            path.push_back(')');
            backtrack(n, open, close + 1);
            path.pop_back();
        }

    }
    bool isValid(string &path) {
        stack<char> stk;
        for (char ele : path) {
            if (ele == '(') {
                stk.push(ele);
            } else {
                if (stk.empty()) {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }

    vector<string> res;
    string path;
};

棋盘问题

【51】N皇后

这里我明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。
在这里插入图片描述

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> path(n,string(n,'.'));
        backtracking(path,n,0);
        return res;
    }
private:
    void backtracking(vector<string> &path,int n,int row){
        if(row == n){
            res.push_back(path);
            return;
        }

        for(int col = 0;col<n;col++){//每一列横向遍历
            //在第几列就push进去
            if(isValid(path,n,row,col)){//验证合法就可以放进去
                path[row][col] = 'Q';//标记
                backtracking(path,n,row+1);//下一行
                path[row][col] = '.';//回溯
            }
        }

    }

    bool isValid(vector<string> &path,int n,int row,int col){
        //不能在同行
        for(int i =0;i<col;i++){
            if(path[row][i] == 'Q'){
                return false;
            }
        }
        
        //不能在同列
        for(int i =0;i<row;i++){
            if(path[i][col] == 'Q'){
                return false;
            }
        }
        //不同在同一条斜线上 45度 135度
        //135度
        for(int i = row-1,j = col-1;i>=0&&j>=0;i--,j--){
            if(path[i][j] == 'Q'){
                return false;
            }
        }
        //45度
        for(int i=row-1,j = col+1;i>=0&&j<n;i--,j++){
            if(path[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> res;//所有可能的结果

};