本周題目難度"Medium",使用語言:C
題目：本周的題目和上周的基本上是一樣的洼怔，就是給你一個(gè)組合和一個(gè)數(shù)，讓你找出加起來和為那個(gè)數(shù)的組合篇裁，具體解釋看上周的題目,懶得解釋了^v^.區(qū)別呢就是這次不能重復(fù)使用組合里的數(shù)了间护，然后就是和上周的一樣不能出現(xiàn)重復(fù)的組合是己。
思路：和上周的一樣雳攘，多一步去重就好了。所以就不解釋了枫笛，直接上代碼吨灭。
//排序（這個(gè)排序我們已經(jīng)是第四次用了，不解釋）
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);
}
//這是我寫的回溯算法相應(yīng)的參數(shù)在主函數(shù)有解釋
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++) {
//這里避免了一次的重復(fù)刑巧，意思就是如果一個(gè)數(shù)字重復(fù)出現(xiàn)第二次就不用遍歷了喧兄，其實(shí)可以考慮在這里進(jìn)行去重的，有興趣的小伙伴可以想想啊楚，這里去重會(huì)大大提高算法的效率
if (i != 0 && *index == 0 && candidates[i]==candidates[i-1]) continue;
*sum += candidates[i];
result[*index] = candidates[i];
*index += 1;
//各項(xiàng)和等于target
if (*sum == target) {
//記錄集合內(nèi)數(shù)字的個(gè)數(shù)
tempColumnSizes[*count] = *index;
//記錄這個(gè)集合
tempArray[*count] = malloc(sizeof(int) * *index);
for(int j = 0; j < *index; j++) {
tempArray[*count][j] = result[j];
}
//集合的個(gè)數(shù)+1
*count += 1;
//index和sum回退一個(gè)拼湊新的集合
*index -= 1;
*sum -= candidates[i];
break;
//各項(xiàng)和小于target
}else if (*sum < target) {
//調(diào)用回溯算法將集合的數(shù)字再加一個(gè)
combinationSumTool(candidates, candidatesSize, target, tempColumnSizes, i+1, sum, index, result, count, tempArray);
//index和sum回退一個(gè)拼湊新的集合
*index -= 1;
*sum -= candidates[i];
//各項(xiàng)和大于target
}else {
//index和sum回退一個(gè)拼湊新的集合
*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;
//記錄下標(biāo)
int *index = malloc(sizeof(int));
*index = 0;
//記錄數(shù)組
int *result = malloc(sizeof(int) * target);
//記錄個(gè)數(shù)
int *count = malloc(sizeof(int));
*count = 0;
//定義數(shù)組容器
int** tempArray = malloc(sizeof(int*) * 200);
//定義長度容器
int* tempColumnSizes = malloc(sizeof(int) * 200);
//調(diào)用回溯算法
combinationSumTool(candidates, candidatesSize, target, tempColumnSizes, 0, sum, index, result, count, tempArray);
columnSizes[0] = malloc(sizeof(int) * *count);
//如果只有一個(gè)結(jié)果吠冤，那肯定沒有重復(fù)的
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++) {
//默認(rèn)不相同
int isEqual = 0;
for (int j = i+1; j < *count; j++) {
//先比個(gè)數(shù)恭理，不一樣就直接比下一個(gè)
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--;
}
//如果相同拯辙，標(biāo)記退出
if (!num) {
isEqual = 1;
break;
}
}
if (!isEqual) {
//將第i個(gè)記錄進(jìn)去
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的人太少太少了。涯保。诉濒。
