回溯算法

回溯算法的详解

什么是回溯法

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

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

回溯法解决的问题

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

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

相信大家看着这些之后会发现，每个问题，都不简单！

另外，会有一些同学可能分不清什么是组合，什么是排列？

组合是不强调元素顺序的，排列是强调元素顺序。

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

记住组合无序，排列有序，就可以了。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

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

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

回溯法模板

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

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。

回溯算法中函数返回值一般为void。

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

但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。

回溯函数伪代码如下：

void backtracking(参数)

回溯函数终止条件

既然是树形结构，那么我们在讲解二叉树的递归 (opens new window)的时候，就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

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

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

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

回溯搜索的遍历过程

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

如图：

注意图中，我特意举例集合大小和孩子的数量是相等的！

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

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

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

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

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

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

这份模板很重要，后面做回溯法的题目都靠它了！

如果从来没有学过回溯算法的录友们，看到这里会有点懵，后面开始讲解具体题目的时候就会好一些了，已经做过回溯法题目的录友，看到这里应该会感同身受了。

总结

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

回溯算法例题

1 组合问题

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

解析

//全局变量
//使用算法：回溯算法、
int** ans;
int ansTop;
int pathTop;
int* path;

void pathtracking(int n, int k, int startIndex)
{
    //当path中元素个数为k个时，我们需要将path数组放入ans二维数组中
    if(pathTop == k)
    {
        //path数组为我们动态申请，若直接将其地址放入二维数组
        //path数组中的值会随着我们回溯而逐渐变化
        //因此创建新的数组存储path中的值
        int* temparr = (int*)malloc(sizeof(int)*k);
        for(int i = 0; i<k; i++)
        {
            temparr[i] = path[i];
        }
        ans[ansTop++] = temparr;

        return;
    }

    for(int i = startIndex; i<=n; i++)
    {
        //将当前结点放入path数组
        path[pathTop++] = i;
        //进行递归
        pathtracking(n,k,i+1);
        //进行回溯，将数组最上层结点弹出
        pathTop--;
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes)
{
    //path数组存储符合条件的结果
    path = (int*)malloc(sizeof(int)*k);
    //ans二维数组存储符合条件的结果数组的集合。（数组足够大，避免极端情况）
    ans = (int**)malloc(sizeof(int*)*10000);
    pathTop = 0;
    ansTop = 0;
	
    //回溯算法
    pathtracking( n, k, 1);
    *returnSize = ansTop; //最后的返回大小为ans数组大小
    //returnColumnSizes数组存储ans二维数组对应下标中一维数组的长度（都为k）
    (*returnColumnSizes) = (int*)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i<(*returnSize); i++)
    {
        (*returnColumnSizes)[i] = k;
    }
    //返回ans二维数组
    return ans;
}

2 分割回文串

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

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

我的代码：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
bool isPalindrome(char* s)
{
    for(int i = 0; i<strlen(s)/2; i++)
    {
        if(s[i] != s[strlen(s)-i-1])
        {
            return false;
        }
    }
    return true;
}

char*** ans;
int ansTop;
int* anslengths;

char** path;
int pathTop;

bool isPalindromeArrs()
{
    for(int i = 0; i<=pathTop; i++)
    {
        if(!isPalindrome(path[i]))
        {
            return false;
        }
    }
    return true;
}

bool isFull(char* s)
{
    int sum = 0;
    for(int i = 0; i<pathTop; i++)
    {
        sum += strlen(path[i]);
    }
    if(sum == strlen(s))
        return true;
    else 
        return false;
}



void pathtracking(char* s, int pos)
{
    if(isPalindromeArrs() && strlen(path[0])!=0 && isFull(s))
    {
        char** temp = (char**)malloc(sizeof(char*)*(pathTop+1));
        
        for(int i = 0; i<= pathTop; i++)
        {
            temp[i] = (char*)malloc(sizeof(char)*(strlen(path[i])+1));
            strcpy(temp[i], path[i]);
        }
        anslengths[ansTop] = pathTop;
        ans[ansTop++] = temp;
    }

    if(pos == strlen(s))
    {
        return;
    }

    for(int i = pos; i<strlen(s); i++)
    {
        for(int j = pos; j<=i; j++)
        {
            path[pathTop][j-pos] = s[j];
        }
        path[pathTop][i+1-pos] = '\0';
        pathTop++;
        for(int j = i+1; j<strlen(s); j++)
        {
            path[pathTop][j-i-1] = s[j];
        }
        path[pathTop][strlen(s)-i-1] = '\0';
        pathtracking(s,i+1);
        pathTop--;
    }
}

char *** partition(char * s, int* returnSize, int** returnColumnSizes)
{
    ans = (char***)malloc(sizeof(char**)*100000);
    anslengths = (int*)malloc(sizeof(int)*100000);
    path = (char**)malloc(sizeof(char*)*20);
    for(int i = 0; i<20; i++)
    {
        path[i] = (char*)malloc(sizeof(char)*20);
        memset(path[i],0,sizeof(char)*20);
    }
    ansTop = 0;
    pathTop = 0;

    pathtracking(s, 0);

    *returnSize = ansTop;
    *returnColumnSizes = anslengths;

    return ans;
}

高手的代码（极大缩短时间的消耗）

char** path;
int pathTop;
char*** ans;
int ansTop = 0;
int* ansSize;

//将path中的字符串全部复制到ans中
void copy() 
{
    //创建一个临时tempPath保存path中的字符串
    char** tempPath = (char**)malloc(sizeof(char*) * pathTop);
    int i;
    for(i = 0; i < pathTop; i++) 
    {
        tempPath[i] = path[i];
    }
    //保存tempPath
    ans[ansTop] = tempPath;
    //将当前path的长度（pathTop）保存在ansSize中
    ansSize[ansTop++] = pathTop;
}

//判断字符串是否为回文字符串
bool isPalindrome(char* str, int startIndex, int endIndex) 
{
    //双指针法：当endIndex（右指针）的值比startIndex（左指针）大时进行遍历
    while(endIndex >= startIndex) 
    {
        //若左指针和右指针指向元素不一样，返回False
        if(str[endIndex--] != str[startIndex++])
            return 0;
    }
    return 1;
}

//切割从startIndex到endIndex子字符串
char* cutString(char* str, int startIndex, int endIndex) 
{
    //开辟字符串的空间
    char* tempString = (char*)malloc(sizeof(char) * (endIndex - startIndex + 2));
    int i;
    int index = 0;
    //复制子字符串
    for(i = startIndex; i <= endIndex; i++)
        tempString[index++] = str[i];
    //用'\0'作为字符串结尾
    tempString[index] = '\0';
    return tempString;
}

void backTracking(char* str, int strLen,  int startIndex) 
{
    if(startIndex >= strLen) 
    {
        //将path拷贝到ans中
        copy();
        return ;
    }

    int i;
    for(i = startIndex; i < strLen; i++) 
    {
        //若从subString到i的子串是回文字符串，将其放入path中 ****我没想到的思路****
        if(isPalindrome(str, startIndex, i)) 
        {
            path[pathTop++] = cutString(str, startIndex, i);
        }
        //若从startIndex到i的子串不为回文字符串，跳过这一层 ****我没想到的思路****
        else 
        {
            continue;
        }
        //递归判断下一层
        backTracking(str, strLen, i + 1);
        //回溯，将path中最后一位元素弹出
        pathTop--;
    }
}

char*** partition(char* s, int* returnSize, int** returnColumnSizes)
{
    int strLen = strlen(s);
    //因为path中的字符串最多为strLen个（即单个字符的回文字符串），所以开辟strLen个char*空间
    path = (char**)malloc(sizeof(char*) * strLen);
    //存放path中的数组结果
    ans = (char***)malloc(sizeof(char**) * 40000);
    //存放ans数组中每一个char**数组的长度
    ansSize = (int*)malloc(sizeof(int) * 40000);
    ansTop = pathTop = 0;

    //回溯函数
    backTracking(s, strLen, 0);

    //将ansTop设置为ans数组的长度
    *returnSize = ansTop;
    //设置ans数组中每一个数组的长度
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    int i;
    for(i = 0; i < ansTop; ++i) 
    {
        (*returnColumnSizes)[i] = ansSize[i];
    }
    return ans;
}

3 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

解答

char** result;
bool* used;
int g_found;

int cmp(const void *str1, const void *str2)
{
    const char **tmp1 = *(char**)str1;
    const char **tmp2 = *(char**)str2;
    int ret = strcmp(tmp1[0], tmp2[0]);
    if (ret == 0) 
    {
        return strcmp(tmp1[1], tmp2[1]);
    }
    return ret;
}
void backTracking(char *** tickets, int ticketsSize, int* returnSize, char*s, char** result, bool* used)
{
    if(*returnSize == ticketsSize + 1)
    {
        g_found = 1;
        return;
    }
    for(int i = 0; i<ticketsSize; i++)
    {
        if((used[i] == false) && (strcmp(s, tickets[i][0]) == 0))
        {
            result[*returnSize] = (char*)malloc(sizeof(char)*4);
            memcpy(result[*returnSize], tickets[i][1], sizeof(char) * 4);
            (*returnSize)++;
            used[i] = true;
            if ((*returnSize) == ticketsSize + 1) 
            {
                g_found = 1;
                return;
            }
            backTracking(tickets, ticketsSize, returnSize, tickets[i][1], result, used);
            if(g_found) 
                return;
            (*returnSize)--;
            used[i] = false;
        }
    }
    return;
}

char ** findItinerary(char *** tickets, int ticketsSize, int* ticketsColSize, int* returnSize)
{
    result = (char**)malloc(sizeof(char*)*(ticketsSize+1));
    result[0] = (char*)malloc(sizeof(char)*4);
    memcpy(result[0], "JFK", sizeof(char)*4);
    used = malloc(sizeof(bool)*(ticketsSize));
    memset(used, false, sizeof(bool)*ticketsSize);
    g_found = 0;
    *returnSize = 1;
    qsort(tickets,ticketsSize,sizeof(tickets[0]), cmp);

    backTracking(tickets, ticketsSize, returnSize,"JFK", result,used);

    *returnSize = ticketsSize+1;
    return result;
}

4 括号生成

力扣 22

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

分析

我们在什么情况下添加左括号呢？很明显，最多能添加 n 个左括号，在递归调用的时候，在能传递到底层的公用字符串种先添加 "("，然后 left-1，递归调用即可。

什么时候添加右括号呢？当左括号个数大于右括号的个数时添加右括号。

向下搜索要满足下面两个条件：

插入数量不超过 n。
可以插入 ) 的前提时 ( 的数量大于 )

回溯法代码套路是使用两个变量：res 和 path ，res 表示最终的结果，path 保存已经走过的路径。如果搜到一个状态满足要求就将 path 放入 res 中。

代码后面的判断条件都是 if，而不是 elif，因为是满足两个条件的任意一个就可以继续向下搜索，而不是同时只能满足其中的一个。

class Solution{
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        int lc = 0, rc = 0;
        dfs(res, "", n, lc, rc);
        return res;
    }
    void dfs(vector<string>& res, string path, int n, int lc, int rc)
    {
        if (rc > lc || lc > n || rc > n) return;
        if (lc == rc && lc == n) 
        {
            res.push_back(path);
            return;
        }
        dfs(res, path + '(', n, lc + 1, rc);
        dfs(res, path + ')', n, lc, rc + 1);
    }
};

卡布叻_米菲的世界

什么是回溯法

回溯法解决的问题

如何理解回溯法

回溯法模板

总结

回溯算法例题

1 组合问题

2 分割回文串

3 重新安排行程

4 括号生成