/**

 * Return an array of arrays of size *returnSize.

 * Note: The returned array must be malloced, assume caller calls free().

 */

int** fourSum(int* nums, int numsSize, int target, int* returnSize) {

    quickSort(nums, , numsSize-);

    int* elem = malloc(sizeof(int)*);

    int** returnArray = malloc(sizeof(int*)*);

    nSum(nums, numsSize, target, elem, returnArray, returnSize, );

    return returnArray;

}

void twoSum(int* nums, int numsSize, int target, int* elem, int** returnArray, int* returnSize){

        int j = ;

        int k = numsSize-;

        while(j<k){

            if(nums[j]+nums[k] < target) j++;

            else if(nums[j]+nums[k] > target) k--;

            else{

               elem[] = nums[j];

               elem[] = nums[k];

               int* returnElem = malloc(sizeof(int)*);

               memcpy(returnElem, elem,sizeof(int)*);

               returnArray[*returnSize] = returnElem;

               (*returnSize)++;

               j++;

               k--;

               while(j<k && nums[j]==nums[j-]) j++; //To avoid duplicate triplets

               while(j<k && nums[k]==nums[k+]) k--;

            }

        }

}

void nSum(int* nums, int numsSize, int target, int* elem, int** returnArray, int* returnSize, int N){

    if(N<=) {

        twoSum(nums, numsSize, target, elem, returnArray, returnSize);

        return;

    }

    N--;

    for(int i = ; i < numsSize-N; i++){

        elem[-N-] = nums[i];

        nSum(nums+i+, numsSize-i-, target-nums[i], elem, returnArray, returnSize, N);

        while(nums[i+]==nums[i]) i++; //To avoid duplicate triplets

    }

}

void quickSort(int* nums, int start, int end){

    int p1 = start+;

    int p2 = end;

    int tmp;

    while(p1 <= p2){

        while(p1 <= p2 && nums[p1] <= nums[start]){

            p1++;

        }

        while(p1 <= p2 && nums[p2] > nums[start]){

            p2--;

        }

        if(p1 < p2){

            tmp = nums[p1];

            nums[p1] = nums[p2];

            nums[p2] = tmp;

            p1++;

            p2--;

        }

    }

    //put the sentinel at the end of the first subarray

    if(start!=p2){

    tmp = nums[start];

    nums[start] = nums[p2];

    nums[p2] = tmp;

    }

    if(start < p2-) quickSort(nums,start, p2-); //sort first subarray (<=sentinel)

    if(p1 < end) quickSort(nums,p1, end); //sort second subarray  (>sentinel)

}