#回溯算法理论基础
能解决的问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
第77题. 组合
给定两个整数 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，pathlength
int *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
找出所有相加之和为 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.电话号码的字母组合
给定一个仅包含数字 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;
}