1+
2+ /**
3+ * Return an array of arrays of size *returnSize.
4+ * The sizes of the arrays are returned as *returnColumnSizes array.
5+ * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
6+ */
7+
8+
9+ // An array with array_size to store each unique combination during backtracking.
10+ struct Combination_Array {
11+ int * array ;
12+ int array_size ;
13+ };
14+
15+ // A function to create a empty Combination_Array.
16+ struct Combination_Array * New (int array_size ) {
17+ struct Combination_Array * comb_array = (struct Combination_Array * )malloc (sizeof (struct Combination_Array ));
18+ comb_array -> array = (int * )malloc (array_size * sizeof (int ));
19+ comb_array -> array_size = array_size ;
20+ return comb_array ;
21+ }
22+
23+ // A generic stack node with void* pointer.
24+ struct Stack {
25+ void * value ;
26+ struct Stack * next ;
27+ };
28+
29+ // A function to create the stack node.
30+ struct Stack * Node (void * value ,struct Stack * next ) {
31+ struct Stack * node = (struct Stack * )malloc (sizeof (struct Stack ));
32+ node -> value = value ;
33+ node -> next = next ;
34+ return node ;
35+ }
36+
37+ // append to the stack.
38+ void append (struct Stack * root ,void * value ) {
39+ struct Stack * node = Node (value ,root -> next );
40+ root -> next = node ;
41+ }
42+
43+ // pop from the stack.
44+ void * pop (struct Stack * root ) {
45+ void * value = root -> next -> value ;
46+ struct Stack * delete_node = root -> next ;
47+ root -> next = root -> next -> next ;
48+ free (delete_node );
49+ return value ;
50+ }
51+
52+ // Recursive backtracking method.
53+ int backtrack (struct Stack * results ,struct Stack * candidates_stack ,int stack_size ,int running_sum ,int * candidates ,int index ) {
54+
55+ if (running_sum == 0 ) {
56+ // create a combination array.
57+ struct Combination_Array * combination = New (stack_size );
58+ // copy the candidates from the candidates_stack to the combination array.
59+ struct Stack * node = candidates_stack ;
60+ for (int i = 0 ;i < stack_size ;i ++ ) {
61+ combination -> array [i ]= * (int * )node -> next -> value ;
62+ node = node -> next ;
63+ }
64+ // append the combination to the results stack.
65+ append (results ,combination );
66+ return 1 ;
67+ }
68+
69+ int returnSize = 0 ;
70+ if (running_sum > 0 ) {
71+ for (int i = index ;i >=0 ;i -- ) {
72+ append (candidates_stack ,& candidates [i ]);
73+ returnSize += backtrack (results ,candidates_stack ,stack_size + 1 ,running_sum - candidates [i ],candidates ,i );
74+ // backtrack by poping the candidate from the candidate_stack.
75+ pop (candidates_stack );
76+ }
77+ }
78+
79+ return returnSize ;
80+ }
81+
82+
83+ int * * combinationSum (int * candidates ,int candidatesSize ,int target ,int * returnSize ,int * * returnColumnSizes ){
84+
85+ // A candidates_stack to track all possible combinations of candidates during backtracking.
86+ struct Stack * candidates_stack = Node (NULL ,NULL );
87+ // A results stack to store each combination solution on the stack during backtracking.
88+ struct Stack * results = Node (NULL ,NULL );
89+
90+ // The backtracking method returns the total number of possible combinations (the final result size).
91+ * returnSize = backtrack (results ,candidates_stack ,0 ,target ,candidates ,candidatesSize - 1 );
92+
93+ // prepare the result array.
94+ int * * result_array = (int * * )malloc (* returnSize * sizeof (int * ));
95+ * returnColumnSizes = (int * )malloc (* returnSize * sizeof (int ));
96+
97+ for (int i = 0 ;i < * returnSize ;i ++ ) {
98+ // pop() each solution from the results stack to the results array.
99+ struct Combination_Array * combination = (struct Combination_Array * )pop (results );
100+ result_array [i ]= combination -> array ;
101+ returnColumnSizes [0 ][i ]= combination -> array_size ;
102+ free (combination );
103+ }
104+ // finally free the results stack and the candidates stack.
105+ free (results );
106+ free (candidates_stack );
107+ return result_array ;
108+
109+ }