update leetcode solution

1 files changed, 46 insertions, 0 deletions

diff --git a/Computer_Science/leetcode/39-combination_sum.c b/Computer_Science/leetcode/39-combination_sum.c
new file mode 100644
index 0000000..23695c5
--- /dev/null
+++ b/Computer_Science/leetcode/39-combination_sum.c
@@ -0,0 +1,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;
+}