[回溯]leetcode77. 组合(c实现超详细解析)

题目

给定两个整数 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