代码随想录算法训练营第22天-leetcode-回溯算法part01：

#回溯算法理论基础

能解决的问题：

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

第77题. 组合

力扣题目链接(opens new window)

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], 

注意：

1、对于是递归回溯问题，用树图来考虑问题！+使用基本结构

        同时，也要积极分析如何剪枝

2、路径类问题的标准套路：

        在函数外开辟path 和 ans 一层空间 ans=（int**）malloc：一层空间，二层空间还没开辟

        终止条件 if（一条路径完成了） 把path放入ans数组

                先开辟ans的二层空间，ans【i】=（int*）malloc

                放入path的过程需要用循环一个个放入，直接=path的话，后面会随path修改而修改

        递归体：填充path

3、报错分析：

遇见heap堆错误，找malloc相关的；遇见stack栈报错，找函数内数组是否越界

4、returnsize 和 return column

*returnsize 在函数调用中无需&，且指向个数，而非下标

column的赋值过程：*column是正常数组，先为*column开辟空间，*column【第几个，<returnsize】=ans【第几个】有多少个二层元素

分析：

代码：

void bf(int *path,int n,int start,int k,int *pathlength,int **ans,int *returnSize){if(*pathlength == k-1){//路径类问题的标准输出ans[++(*returnSize)]=(int *)malloc(sizeof(int)*k);for (int i=0;i<k;i++){ans[*returnSize][i]=path[i];}return;}for(int i=start;i<=n-(k-*pathlength-2);i++){//遍历各个树//剪枝：如果后面全放进去，也达不到k个个数，那么就不考虑了path[++(*pathlength)]=i;bf(path,n,i+1,k,pathlength,ans,returnSize);(*pathlength)--;//回溯 步骤！！}
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {int **ans=(int **)malloc(sizeof(int *)*200001);*returnSize=-1;int pathlength=-1;//考虑路径，用到path，pathlengthint *path=(int *)malloc(sizeof(int )*k);bf(path,n,1, k, &pathlength,ans,returnSize);//returnsize不需要&(*returnSize)++;//returnsize指向数组的实际大小*returnColumnSizes=(int*)malloc(sizeof(int )*(*returnSize));//column的意义for(int i=0;i<(*returnSize);i++){(*returnColumnSizes)[i]=k;}return ans;
}

216.组合总和III

力扣题目链接(opens new window)

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]

void bp(int **ans,int *size,int *path,int *p,int k,int n,int start,int sum){if(sum>n) return;//剪枝if(sum==n && *p==k){ans[*size]=(int *)malloc(sizeof(int)*k);for (int i=0;i<k;i++){ans[*size][i]=path[i];}(*size)++;return;//不要忘记写return}else if(*p==k){//另外一种终止情况return;}for(int i=start;i<=9;i++){path[(*p)++]=i;bp(ans, size, path, p,  k,  n, i+1,  sum+i);//i+1，而不是start+1(*p)--;}
}int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {int **ans=(int **)malloc(sizeof(int *)*500);int size=0;int *path=(int *)malloc(sizeof(int)*k);int p=0;bp(ans, &size,path, &p, k, n, 1, 0);*returnSize=size;*returnColumnSizes=(int *)malloc(sizeof(int)*(size));for (int i=0;i<size;i++){(*returnColumnSizes)[i]=k;//要加括号}return ans;}

17.电话号码的字母组合

力扣题目链接(opens new window)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

char phoneMap[11][5] = {"\0", "\0", "abc\0", "def\0", "ghi\0", "jkl\0", "mno\0", "pqrs\0", "tuv\0", "wxyz\0"};void bp(char**ans,int *size,char *path,int *p,int len,char* digits,int d){if(*p==len){ans[*size] =(char*)malloc(sizeof(char)*(len+1));for(int i=0;i<len;i++){ans[*size][i]=path[i];printf("%c",path[i]);}        ans[*size][len]='\0';printf("\n");(*size)++;return;}int number= digits[d]-'0';char * nowd=phoneMap[number];int dlen=strlen(nowd);for(int i=0;i<dlen;i++){char new=nowd[i];path[(*p)++]=new;bp(ans, size, path,p, len, digits,d+1);(*p)--;}}char** letterCombinations(char* digits, int* returnSize) {int len=strlen(digits);char**ans=(char**)malloc(sizeof(char*)*pow(4,len));int size=0;if (len==0) {*returnSize=0;return ans;}char *path=(char*)malloc(sizeof(char)*(len+1));int p=0;bp(ans,&size, path, &p, len, digits, 0);*returnSize=size;return ans;}