本周题目难度"Medium",使用语言:C
题目：本周的题目和上周的基本上是一样的，就是给你一个组合和一个数，让你找出加起来和为那个数的组合，具体解释看上周的题目,懒得解释了^v^.区别呢就是这次不能重复使用组合里的数了，然后就是和上周的一样不能出现重复的组合。
思路：和上周的一样，多一步去重就好了。所以就不解释了，直接上代码。
//排序（这个排序我们已经是第四次用了，不解释）
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* tempColumnSizes, int k,int* sum, int* index, int* result, int* count, int** tempArray) {
//开始遍历
for (int i = k; i < candidatesSize; i++) {
//这里避免了一次的重复，意思就是如果一个数字重复出现第二次就不用遍历了，其实可以考虑在这里进行去重的，有兴趣的小伙伴可以想想，这里去重会大大提高算法的效率
if (i != 0 && *index == 0 && candidates[i]==candidates[i-1]) continue;
*sum += candidates[i];
result[*index] = candidates[i];
*index += 1;
//各项和等于target
if (*sum == target) {
//记录集合内数字的个数
tempColumnSizes[*count] = *index;
//记录这个集合
tempArray[*count] = malloc(sizeof(int) * *index);
for(int j = 0; j < *index; j++) {
tempArray[*count][j] = result[j];
}
//集合的个数+1
*count += 1;
//index和sum回退一个拼凑新的集合
*index -= 1;
*sum -= candidates[i];
break;
//各项和小于target
}else if (*sum < target) {
//调用回溯算法将集合的数字再加一个
combinationSumTool(candidates, candidatesSize, target, tempColumnSizes, i+1, sum, index, result, count, tempArray);
//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** combinationSum2(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
//排序
quickSort(candidates,0,candidatesSize-1);
//累加和
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** tempArray = malloc(sizeof(int*) * 200);
//定义长度容器
int* tempColumnSizes = malloc(sizeof(int) * 200);
//调用回溯算法
combinationSumTool(candidates, candidatesSize, target, tempColumnSizes, 0, sum, index, result, count, tempArray);
columnSizes[0] = malloc(sizeof(int) * *count);
//如果只有一个结果，那肯定没有重复的
if (*count < 2) {
*returnSize = *count;
for (int i = 0; i < *count; i++) {
columnSizes[0][i] = tempColumnSizes[i];
}
return tempArray;
}
//去重，就这里和上周不一样
int** returnArray = malloc(sizeof(int*)* *count);
int len = 0;
for (int i = 0; i < *count-1; i++) {
//默认不相同
int isEqual = 0;
for (int j = i+1; j < *count; j++) {
//先比个数，不一样就直接比下一个
if (tempColumnSizes[i] != tempColumnSizes[j]) continue;
int num = tempColumnSizes[i];
for (int k = 0; k < tempColumnSizes[i]; k++) {
if (tempArray[i][k] != tempArray[j][k]) break;
num--;
}
//如果相同，标记退出
if (!num) {
isEqual = 1;
break;
}
}
if (!isEqual) {
//将第i个记录进去
columnSizes[0][len] = tempColumnSizes[i];
returnArray[len] = malloc(sizeof(int) * tempColumnSizes[i]);
for(int l = 0; l < tempColumnSizes[i]; l++) {
returnArray[len][l] = tempArray[i][l];
}
len++;
}
}
columnSizes[0][len] = tempColumnSizes[*count-1];
returnArray[len] = malloc(sizeof(int) * tempColumnSizes[*count-1]);
for(int l = 0; l <= tempColumnSizes[*count-1]; l++) {
returnArray[len][l] = tempArray[*count-1][l];
}
*returnSize = len+1;
return returnArray;
}
效率一般，用C的人太少太少了。。。
