【回溯算法】对Day52组合问题的剪枝优化

在组合问题中，我们其实可以省略很多次的for循环遍历进行优化。

例如，当n=4、k=4时，我们只能从1进行遍历。从2之后进行的遍历就没有意义了

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了

优化过程：

1. 已经选择的元素个数：path.size
2. 还需要的元素个数：k-path.size
3. 至多能从该位置遍历path，path中的数字个数才能满足：n-(k-path.size)+1

因此，我们的for循环遍历语句便可以改成：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

全局代码：

int* path;
int pathTop;
int** ans;
int ansTop;

void backtracking(int n, int k,int startIndex) {
    //当path中元素个数为k个时，我们需要将path数组放入ans二维数组中
    if(pathTop == k) {
        //path数组为我们动态申请，若直接将其地址放入二维数组，path数组中的值会随着我们回溯而逐渐变化
        //因此创建新的数组存储path中的值
        int* temp = (int*)malloc(sizeof(int) * k);
        int i;
        for(i = 0; i < k; i++) {
            temp[i] = path[i];
        }
        ans[ansTop++] = temp;
        return ;
    }

    int j;
    for(j = startIndex; j <= n- (k - pathTop) + 1;j++) {
        //将当前结点放入path数组
        path[pathTop++] = j;
        //进行递归
        backtracking(n, k, j + 1);
        //进行回溯，将数组最上层结点弹出
        pathTop--;
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    //path数组存储符合条件的结果
    path = (int*)malloc(sizeof(int) * k);
    //ans二维数组存储符合条件的结果数组的集合。（数组足够大，避免极端情况）
    ans = (int**)malloc(sizeof(int*) * 10000);
    pathTop = ansTop = 0;

    //回溯算法
    backtracking(n, k, 1);
    //最后的返回大小为ans数组大小
    *returnSize = ansTop;
    //returnColumnSizes数组存储ans二维数组对应下标中一维数组的长度（都为k）
    *returnColumnSizes = (int*)malloc(sizeof(int) *(*returnSize));
    int i;
    for(i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = k;
    }
    //返回ans二维数组
    return ans;
}