每周一道算法题(三十二)

本周题目难度级别'Medium'，使用语言：C

题目：给你一个集合candidates和一个数字target，让你用集合中的数字组成一些新的集合，要求新的集合中的各项数字的和为target，candidates中的数字可以重复使用。在接下来的举例中我会将C语言里面的参数一并解释出来。

eg:给你一个集合candidates[2, 3, 6, 7]和一个数target：7（并告知你们candidates中数字的个数candidatesSize：4），你找出来返回的组合是：[ [7],[2, 2, 3] ]并且要将这个集合里包含的集合个数2赋值给returnSize，还要将这个集合里包含的每一个集合里数字的个数（1，3）赋值给columnSizes，需要注意的是返回的组合和columnSizes需要手动开辟空间。

思路：这道题我们也用到了回溯算法，就是一个一个带入然后和target进行比较，如果等于target就记录；如果小于就再加一个数；如果大于就回退一个数然后再带入下一个数字。
下面根据代码来解释（从combinationSum这个函数开始看，英文的注释我已经在例子中都解释了）：

//排序（这个排序我们已经是第三次用了，不解释）
 void quickSort(int* nums,int first,int end){
    int temp,l,r;
    if(first>=end)return;
    temp=nums[first];
    l=first;r=end;
    while(l<r){
        while(l<r && nums[r]>=temp)r--;
        if(l<r)nums[l]=nums[r];
        while(l<r && nums[l]<=temp)l++;
        if(l<r)nums[r]=nums[l];
    }
    nums[l]=temp;
    quickSort(nums,first,l-1);
    quickSort(nums,l+1,end);
}
//这是我写的回溯算法相应的参数在主函数有解释
void combinationSumTool(int* candidates, int candidatesSize, int target, int** columnSizes, int k,int* sum, int* index, int* result, int* count, int** returnArray) {
    //开始遍历
    for (int i = k; i < candidatesSize; i++) {
        *sum += candidates[i];
        result[*index] = candidates[i];
        *index += 1;
        //各项和等于target
        if (*sum == target) {
            //记录集合内数字的个数
            columnSizes[0][*count] = *index;
            //记录这个集合
            returnArray[*count] = malloc(sizeof(int) * *index);
            for(int j = 0; j < *index; j++) {
                returnArray[*count][j] = result[j];
            }
            //集合的个数+1
            *count += 1;
            //index和sum回退一个拼凑新的集合
            *index -= 1;
            *sum -= candidates[i];
            break;
        //各项和小于target
        }else if (*sum < target) {
            //调用回溯算法将集合的数字再加一个
            combinationSumTool(candidates, candidatesSize, target, columnSizes, i, sum, index, result, count, returnArray);
            //index和sum回退一个拼凑新的集合
            *index -= 1;
            *sum -= candidates[i];
        //各项和大于target
        }else {
            //index和sum回退一个拼凑新的集合
            *index -= 1;
            *sum -= candidates[I];
            break;（由于是从小到大排序的，后面的更大，就不用继续遍历了）
        }
    }
}
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
    //排序
    quickSort(candidates,0,candidatesSize-1);
    //开辟空间
    columnSizes[0] = malloc(sizeof(int) * 150);
    //累加和
    int *sum = malloc(sizeof(int));
    *sum = 0;
    //记录下标
    int *index = malloc(sizeof(int)); 
    *index = 0;
    //记录数组
    int *result = malloc(sizeof(int) * target);
    //记录个数
    int *count = malloc(sizeof(int));
    *count = 0;
    //定义返回数组
    int** returnArray = malloc(sizeof(int*) * 150);
    //调用回溯算法(0是从第几个开始遍历)
    combinationSumTool(candidates, candidatesSize, target, columnSizes, 0, sum, index, result, count, returnArray);
    *returnSize = *count;
    return returnArray;
}

效率还是比较高的，题目本身不难，难点是对columnSizes这个参数的理解，完全无法理解为什么columnSizes要用二维指针而不用一维指针，一维指针完全够用了。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!