1.什么是回溯

顾名思义，回溯就是回头的意思。比如我们要达到一个目的地，但是我们面前有三条路，并且只有一条路是可以到达目的地的，因此我们需要一条一条去尝试，如果不行的话就得回到原点，选择下一条路进行尝试，这种就叫做回溯。
在我们做题中，常见的组合问题，路径问题，使用回溯法，往往事半功倍。

2.解题方法

3.实战演练

3.1路径的总和

题目：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

题目链接

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路径总和貮

题目：
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
题目链接

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

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子集

题目：
给你一个整数数组 nums ，数组中的素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
题目链接

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<numsSize;i++)//每次都从0下标开始读取素，同时有标记数组判断是否可以读取 { 
    if(!arr[i]) { 
    temp[temp_sub]=nums[i]; arr[i]=1;//进行标记 } else continue; GetNum(nums,arr,numsSize, returnSize, returnColumnSizes,ret,temp,temp_sub+1); arr[i]=0;//取消标记 } } int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ 
    int **ret=(int **)malloc(sizeof(int*)*1000); *returnSize=0;//行坐标 *returnColumnSizes=(int *)calloc(1000,sizeof(int));//列坐标 int *temp=(int *)malloc(sizeof(int)*1000);//临时装纳数组素 int *arr=(int *)calloc(numsSize,sizeof(int));//标记数组，用0,1来进行标记 GetNum(nums,arr,numsSize, returnSize, returnColumnSizes,ret,temp,0); return ret; } 

3.5全排列貮

题目：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
题目链接

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

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<numsSize;i++) { 
    if(i-1>=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组合

题目：
给定两个整数 n 和 k，返回 1 … n 中所有可能的 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; }