1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <stdio.h>
#include <stdlib.h>
/**
* 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().
*/
void backtracking(int** result, int* tmp, int* candidates, int candidatesSize, int left, int start, int** columnSizes, int* returnSize)
{
if(left == 0) {
*(result + *returnSize) = malloc(*(*columnSizes + *returnSize) * sizeof(int));
for(int i = 0; i < *(*(columnSizes + *returnSize)); i++)
*(*(result + *returnSize) + i) = tmp[i];
++*returnSize;
} else if(left > 0) {
tmp[*(*(columnSizes + *returnSize))] = candidates[start];
++*(*(columnSizes + *returnSize));
for(int i = start; i < candidatesSize; i++)
backtracking(result, tmp, candidates, candidatesSize, left, start, columnSizes, returnSize);
--*(*(columnSizes + *returnSize));
}
}
int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
int i;
int **result;
int tmp[100];
result = malloc(sizeof(int *) * 100);
columnSizes = malloc(sizeof(int) * 100);
*returnSize = 0;
for(i = 0; i < 100; i++) {
*(*columnSizes + i) = 0;
}
if(candidatesSize == 0)
return NULL;
backtracking(result, tmp, candidates, candidatesSize, target, 0, columnSizes, returnSize);
return result;
}
int main()
{
return 0;
}
|
