給定一個候選人編號的集合?candidates
?和一個目標數?target
?,找出?candidates
?中所有可以使數字和為?target
?的組合。
candidates
?中的每個數字在每個組合中只能使用?一次?。
注意:解集不能包含重復的組合。?
示例?1:
輸入: candidates =?[10,1,2,7,6,1,5]
, target =?8
, 輸出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例?2:
輸入: candidates =?[2,5,2,1,2], target =?5, 輸出: [ [1,2,2], [5] ]
提示:
1 <=?candidates.length <= 100
1 <=?candidates[i] <= 50
1 <= target <= 30
答案如下:
void zuhe2(int target, int idx, int* temp, int tempSize, int** res, int*** pRes, int* returnSize, int** returnColumnSizes, int* pCapacity, int* numCountMap);/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { // LeetCode 40.組合和總和// 先統計數組中每個數的出現個數。由題意 1 <= candidates[i] <= 50, numCountMap[n]表示n在candidates數組中出現的次數int numCountMap[51] = { 0 };for (int i = 0; i < candidatesSize; i++) {numCountMap[candidates[i]]++;}// 1 <= target <= 30 , 而數組candidates中的數最小為1,所以組合子數組長度最大可能為30// 但是不知道組合數量,所以結果數組大小不確定。int tempCapacity = candidatesSize < 30 ? candidatesSize : 30;int* temp = (int*)malloc(tempCapacity * sizeof(int)); if (!temp) return NULL;*returnSize = 0;int capacity = 2; // 初始容量,后續容量不夠再擴容*returnColumnSizes = (int*)malloc(capacity * sizeof(int));int** res = (int**)malloc(capacity * sizeof(int*));if (!res) return NULL;zuhe2(target, 0, temp, 0, res ,&res ,returnSize, returnColumnSizes, &capacity, numCountMap);free(temp);return res;
}void zuhe2(int target, int idx, int* temp, int tempSize, int** res, int*** pRes, int* returnSize, int** returnColumnSizes, int* pCapacity, int* numCountMap) {if (target == 0) {// 已滿足,保存結果int* arr_ = (int*)malloc(tempSize * sizeof(int));if (!arr_) return;memcpy(arr_, temp, tempSize * sizeof(int));// 保存前先檢查容量if (*returnSize == *pCapacity) { // 之前申請的內存滿了,不夠再存儲了,擴容int newCapacity = *pCapacity << 1;int** temp_res = (int**)realloc(res, newCapacity * sizeof(int*));if (!temp_res) return;*pRes = temp_res;*returnColumnSizes = (int*)realloc(*returnColumnSizes, newCapacity * sizeof(int));if (*returnColumnSizes == NULL) return;*pCapacity = newCapacity;}*(*pRes + *returnSize) = arr_;*(*returnColumnSizes + *returnSize) = tempSize; // 該組合的數字個數*returnSize = *returnSize + 1;return;}for (int i = idx; i < 51; i++) {// 先判斷i是否使用過了if (numCountMap[i] == 0) {// 該數使用完了continue;}if (i > target) {break;}// 可以加的情況,選中該數temp[tempSize++] = i;numCountMap[i]--;// 再遞歸選給臨時數組下一位賦值。 注意,這里idx參數值必選傳i,不能傳idx,防止選到重復的組合。組合的臨時數組中當前在選的數還可以選,但前面選過的數不能再選zuhe2(target - i, i, temp, tempSize, res, pRes, returnSize, returnColumnSizes, pCapacity, numCountMap);// 回退,不選這個數了tempSize--;numCountMap[i]++;}
}
測試代碼:
void testLeeCode40(void) { // 組合總和IIint nums[] = { 4,4,2,1,4,2,2,1,3 };int target = 6;int numsSize = sizeof(nums) / sizeof(int);int returnSize; // 用于接受結果二維數組的長度。int* returnColumnSizes; // 用來接受結果二維數組的每個元素(即子數組)的長度int** res = combinationSum2(nums, numsSize, target, &returnSize, &returnColumnSizes);printArr(res, returnSize, returnColumnSizes); // 打印二維數組// 釋放內存for (int i = 0; i < returnSize; i++) {free(res[i]);}free(res);free(returnColumnSizes);
}
運行:
ok.? 但是提交到LeeCode,報錯:
看上去是調用realloc函數時報錯重復釋放內存了。? 但是沒看出來哪里重復釋放內存了。沒懂這個報錯哪來的,我自己機器上沒報錯。怎么辦? 我把二維數組的容量直接設置為1000,1000應該是夠用了,避免了動態擴容數組,提交通過了:
這個疑問點后面再研究。