#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;
}