本周題目難度級別'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;（由于是從小到大排序的，后面的更大斩郎，就不用繼續(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);
//開辟空間
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要用二維指針而不用一維指針肘迎，一維指針完全夠用了。锻煌。妓布。
