本文共 6575 字，大约阅读时间需要 21 分钟。

1.什么是回溯

顾名思义，回溯就是回头的意思。比如我们要达到一个目的地，但是我们面前有三条路，并且只有一条路是可以到达目的地的，因此我们需要一条一条去尝试，如果不行的话就得回到原点，选择下一条路进行尝试，这种就叫做回溯。

2.解题方法

1.将问题描述成树形结构

2.通过树的关系，找出子问题的递归表达式

2.看是否满足剪枝条件

3.实战演练

3.1路径的总和

题目：

bool GetSum(struct TreeNode* root, int targetSum,int count){       if(root==NULL)//到达空节点说明上一节点不成立        return false;    count+=root->val;//将当前的值相加    if(root->left==NULL&&root->right==NULL&&count==targetSum)//到达叶子节点        return true;    return GetSum(root->left,targetSum,count)||GetSum(root->right,targetSum,count);   }bool hasPathSum(struct TreeNode* root, int targetSum){          //二叉树，首先确定一种遍历的方法，遍历一般都是前/中/后序递归    //通过回溯剪枝的方法，如果当前路径上面的值，大于目标值则直接退出(有负数，不能用)    //回溯需要一个变量保存当前节点的值，如果下一节点不满足条件，则进行剪枝    //由于这里条件特殊不能进行剪枝处理    if(root==NULL)        return false;    int  count=0;        return GetSum(root,targetSum,count);}

3.2路径总和貮

题目：

这里是上面那题的变种，因为上面是只需要判断是否有这么一条路径即可，而这个题目需要将所有路径保存起来，因此需要开辟一个二维数组来记录保存的值，还需要一个临时的数组和下标，因为没达到叶子节点前是不清楚当前路径需不需要进行保存的。我们可以将走过的路径都保存在临时数组中，进行一个判断，如果满足当前的条件，就将临时数组拷贝到二维数组中

void GetRoad(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes,int **ret,int* temp,int count,int sub){       if(root==NULL)//前面一个节点就已经不正确        return ;    temp[sub++]=root->val;//保存当前节点    count+=root->val;    if(root->left==NULL&&root->right==NULL&&count==targetSum)//当前路径合法    {           ret[*returnSize]=(int*)malloc(sizeof(int)*sub);//开辟空间        memcpy(ret[*returnSize],temp,sub*sizeof(int));//拷贝        returnColumnSizes[0][*returnSize]=sub;//保存当前二维数组中一维数组元素的个数        (*returnSize)++;//该数组元素保存下来           return ;    }    GetRoad(root->left,targetSum,returnSize,returnColumnSizes,ret,temp,count,sub);//前序遍历    GetRoad(root->right,targetSum,returnSize,returnColumnSizes,ret,temp,count,sub);}int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** returnColumnSizes){       *returnColumnSizes=(int *)calloc(5000,sizeof(int));//用来记录，路径中，节点个数    *returnSize=0;//路径条数    int **ret=(int **)malloc(sizeof(int)*1000);//放路径首元素地址    int *temp=(int *)malloc(1000*sizeof(int));//临时记录路径数组    int count=0;//统计数目    int sub=0;//统计节点个数        GetRoad(root,targetSum,returnSize,returnColumnSizes,ret,temp,count,sub);        return ret;}

3.3子集

题目：

void GetArray(int* nums, int numsSize, int* returnSize, int** returnColumnSizes, int **ret, int *temp,int temp_sub,int sub){   		ret[*returnSize] = (int *)malloc(sizeof(int*)*temp_sub);//给二级指针内的一级指针分配空间,第一次分配的是空		memcpy(ret[*returnSize], temp, sizeof(int)*temp_sub);//将一维数组的内容填入到二维数组之中		(*returnColumnSizes)[*returnSize] = temp_sub;//填入当前二维数组中一维数组的元素个数即当前子集的元素个数		(*returnSize)++;//returnSize为二维数组的行下标，表示二维数组中有多少个元素		for (int i = sub; i < numsSize; i++)		{   			temp[temp_sub] = nums[i];//填入子集			GetArray(nums, numsSize, returnSize, returnColumnSizes, ret, temp, temp_sub+1, i + 1);            //temp_sub+1保证了，下一个元素是进行插入，i+1保证了填入临时数组内的元素不与上一个重复		}}int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){   	//**returnColumnSizes表示的是二维数组中每个一维数组元素中元素的个数	*returnColumnSizes = (int *)calloc(2000,sizeof(int));//给二级指针中的一级指针分配空间，并且初始化为0		int **ret = (int **)malloc(sizeof(int*)* 2000);//nums最多10个元素，即有......种解		*returnSize = 0;//二维数组中，一维数组的个数	int *temp = (int *)malloc(sizeof(int)*10);//每种解最多有10个元素    	GetArray(nums, numsSize, returnSize, returnColumnSizes, ret, temp,0, 0);	return ret;}

3.4全排列

题目：

void GetNum(int* nums,int *arr, int numsSize, int* returnSize, int** returnColumnSizes,int **ret,int *temp,int temp_sub){       if(temp_sub==numsSize)//当元素满足后填充至返回数组    {           ret[*returnSize]=(int*)malloc(sizeof(int)*numsSize);//给二级指针内的一级指针开辟空间        memcpy(ret[*returnSize],temp,sizeof(int)*numsSize);//内容填充        (*returnColumnSizes)[*returnSize]=temp_sub;        (*returnSize)++;//行坐标下移        return;    }        for(int i=0;i

3.5全排列貮

题目：

没错，这题是上题的变种，只是由无重复元素的数组改成了含有重复元素的数组。

如何剪枝：如果数组的元素是杂乱无章的，我们需要将所有的结果拿到后，再进行遍历排重，这样就比较麻烦了。我先给出结论，我们可以将数组排序，让相同的元素在一起，如果填入临时数组的元素和上一个没有标记的元素相同，那么我们就直接剪枝，接下来我证明一下这是为什么。

void GetNum(int *nums,int *arr, int *temp,int numsSize, int *returnSize,int **returnColumnSizes,int **ret,int temp_sub){       if(temp_sub==numsSize)    {           ret[*returnSize]=(int *)malloc(sizeof(int)*numsSize);        memcpy(ret[*returnSize],temp,sizeof(int)*numsSize);        returnColumnSizes[0][*returnSize]=numsSize;        (*returnSize)++;        return ;    }    for(int i=0;i
   
    =0&&arr[i-1]==0&&nums[i-1]==nums[i])//重复元素，剪枝        continue;        if(!arr[i])        {               temp[temp_sub]=nums[i];            arr[i]=1;        }        else        continue;     GetNum(nums,arr, temp,numsSize, returnSize,returnColumnSizes,ret,temp_sub+1);     arr[i]=0;    }}int  ComInt(const int *x,const int *y)//,传进来的是一个序列之中，任意一个元素的地址{   	return *x-*y;}int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){          qsort(nums,numsSize,sizeof(int),ComInt);//排序    int **ret=(int **)malloc(sizeof(int)*2000);    *returnSize=0;    *returnColumnSizes=(int *)calloc(2000,sizeof(int));    int *temp=(int*)malloc(sizeof(int)*2000);    int *arr=(int *)calloc(2000,sizeof(int));//标记数组    GetNum(nums,arr, temp,numsSize, returnSize,returnColumnSizes,ret,0);    return ret;}
   

3.6组合

题目：

找到递归出口：即临时数组中元素个数达到k个，将内容拷贝给放回数组，退出当前递归

void GetNum(int n, int k, int * returnSize,  int **returnColumnSizes,int *temp,int **ret,int temp_sub,int sub){       if(temp_sub==k)//将满足条件的数组拷贝至返回数组    {           ret[*returnSize]=(int *)malloc(sizeof(int)*k);        memcpy(ret[*returnSize],temp,sizeof(int)*k);        returnColumnSizes[0][*returnSize]=k;        (*returnSize)++;        return;    }    for(int i=sub;i<=n;i++)    {           temp[temp_sub]=i;        GetNum(n,  k, returnSize, returnColumnSizes,temp,ret, temp_sub+1,i+1);//i+1保证不会往回走    }}int** combine(int n, int k, int* returnSize, int** returnColumnSizes){       //准备二维数组    int **ret=(int **)malloc(sizeof(int)*15000);    *returnSize=0;    *returnColumnSizes=(int *)malloc(sizeof(int)*15000);    int *temp=(int *)malloc(sizeof(int)*k);//临时保存K个数的数组    GetNum( n, k,  returnSize,  returnColumnSizes,temp,ret,0,1);    return ret;}