#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 current, int currentSize, int left, int* returnSize, int** columnSizes)
{
	if(left < 0)
		return;
	else if(left > 0)
		return backtracking(result, current, currentSize + 1, left, returnSize);
	else {
		*(result + *returnSize) = malloc(sizeof(int) * currentSize);
	}
}

int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
	int i;
	int **result;
	result = malloc(sizeof(int *) * 100);
	if(candidatesSize == 0)
		return NULL;

	for(i = 0; i < candidatesSize; i++) {
		backtracking(result, candidates[i], i + 1, target, returnSize, columnSizes);
	}

	return result;
}