题目
给定两个整数 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]]
代码
int* path;
int pathTOP;
int** ans;
int ansTOP;
void backtracking(int n, int k, int startIndex)//n代表总数 ,k代表每个集合中的个数 ,startIndex代表 每次开始的位置
{
int i = 0;
if (pathTOP == k)//递归终止条件
{
int* temp = (int*)malloc(sizeof(int) * k);
for (i = 0; i < k; i++)
{
temp[i] = path[i];//将path中集合内的每个数 传入 临时的temp中
}
ans[ansTOP++] = temp;//将一个集合传入ans二维数组
return;
}
int j = 0;
for (j = startIndex; j <=n; j++)//for循环从当前位置遍历
{
path[pathTOP++] = j;
backtracking(n, k, j + 1);//递归
pathTOP--; // 回溯
}
//因为我们是通过path_TOP的值来判断递归终止的,若将path_TOP值减一即返回上一层
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes)
{
path = (int*)malloc(sizeof(int) * k);
ans = (int**)malloc(sizeof(int*) * 10000);
ansTOP = 0;
pathTOP = 0;
backtracking(n, k, 1);//假设是1234 即从1开始
*returnSize = ansTOP;//将二维数组的数量传入
*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
int i = 0;
for (i = 0; i < *returnSize; i++)
{
(*returnColumnSizes)[i] = k;
}
return ans;
}
过程分析
1.整体图
这里的红色的数字都代表取 ,例如 红色1代表取1,剩下的数字为 2 3 4
2.为什么不取之前已经用过的红色数字
若在取2后,仍取1,会发现生成一个 组合 2 1,但是由于组合没有顺序, 1 2 与 2 1等价 ,会造成重复
3.取后的数字为什么删除
若不舍去2,会发现生成一个组合 2 2,由于每个集合中不能有重复的元素, 所以不成立。
4.递归展开图
5.逐步分析
1.
想要求k为2的集合组,由于刚开始pathTOP=0,无法进入递归终止条件, 进入for循环中,j=1时,path[0]=1,pathTOP=1 进入递归
2.
当再次进入backtracking时,pathTOP=1 不符合进入递归终止条件, 再次进入for循环中,当 j=2时,path[1]=2, pathTOP=2 ,再次进入递归
3.
当再次进入backtracking时,此时 pathTOP=k=2,符合条件进入递归终止条件中, 将一维数组传入ans中 ,ans[0]=[1,2]
4.
回溯回去后 ,pathTOP--,pathTOP=1
5.
第二次进入for循环时,当 j=3时,path[2]=3,pathTOP=2,再次进入递归中
6.
由于 pathTOP=k=2,满足进入递归终止条件,ans[1]=[1,3] return 返回上一个的for循环中,pathTOP--,pathTOP=1
7.
第三次进入for循环时,j=4,path[2]=4,pathTOP=2,进入递归中
8.
由于 pathTOP=k=2,满足进入递归终止条件,ans[3]=[1,4] return 返回上一个的for循环中,pathTOP--,pathTOP=1
9.
又因为for循环结束,pathTOP--,pathTOP=0