本周題目難度級(jí)別'Medium'，使用語(yǔ)言：C
題目：給你一個(gè)集合candidates和一個(gè)數(shù)字target，讓你用集合中的數(shù)字組成一些新的集合，要求新的集合中的各項(xiàng)數(shù)字的和為target，candidates中的數(shù)字可以重復(fù)使用。在接下來(lái)的舉例中我會(huì)將C語(yǔ)言里面的參數(shù)一并解釋出來(lái)。
eg:給你一個(gè)集合candidates[2, 3, 6, 7]和一個(gè)數(shù)target：7（并告知你們candidates中數(shù)字的個(gè)數(shù)candidatesSize：4），你找出來(lái)返回的組合是：[ [7],[2, 2, 3] ]并且要將這個(gè)集合里包含的集合個(gè)數(shù)2賦值給returnSize，還要將這個(gè)集合里包含的每一個(gè)集合里數(shù)字的個(gè)數(shù)（1，3）賦值給columnSizes，需要注意的是返回的組合和columnSizes需要手動(dòng)開(kāi)辟空間。
思路：這道題我們也用到了回溯算法，就是一個(gè)一個(gè)帶入然后和target進(jìn)行比較，如果等于target就記錄；如果小于就再加一個(gè)數(shù)；如果大于就回退一個(gè)數(shù)然后再帶入下一個(gè)數(shù)字。
下面根據(jù)代碼來(lái)解釋（從combinationSum這個(gè)函數(shù)開(kāi)始看，英文的注釋我已經(jīng)在例子中都解釋了）：
//排序（這個(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** columnSizes, int k,int* sum, int* index, int* result, int* count, int** returnArray) {
//開(kāi)始遍歷
for (int i = k; i < candidatesSize; i++) {
*sum += candidates[i];
result[*index] = candidates[i];
*index += 1;
//各項(xiàng)和等于target
if (*sum == target) {
//記錄集合內(nèi)數(shù)字的個(gè)數(shù)
columnSizes[0][*count] = *index;
//記錄這個(gè)集合
returnArray[*count] = malloc(sizeof(int) * *index);
for(int j = 0; j < *index; j++) {
returnArray[*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, columnSizes, i, sum, index, result, count, returnArray);
//index和sum回退一個(gè)拼湊新的集合
*index -= 1;
*sum -= candidates[i];
//各項(xiàng)和大于target
}else {
//index和sum回退一個(gè)拼湊新的集合
*index -= 1;
*sum -= candidates[I];
break;（由于是從小到大排序的，后面的更大，就不用繼續(xù)遍歷了）
}
}
}
/**
* 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);
//開(kāi)辟空間
columnSizes[0] = malloc(sizeof(int) * 150);
//累加和
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;
//定義返回?cái)?shù)組
int** returnArray = malloc(sizeof(int*) * 150);
//調(diào)用回溯算法(0是從第幾個(gè)開(kāi)始遍歷)
combinationSumTool(candidates, candidatesSize, target, columnSizes, 0, sum, index, result, count, returnArray);
*returnSize = *count;
return returnArray;
}
效率還是比較高的，題目本身不難，難點(diǎn)是對(duì)columnSizes這個(gè)參數(shù)的理解，完全無(wú)法理解為什么columnSizes要用二維指針而不用一維指針，一維指針完全夠用了。。。
