LC0018

void Bubble_Sort(int* nums,int numsSize) {
    int p,i;
    int temp;
    int flag;

    for (p=numsSize-1;p>=0;p--) {
        flag=0;
        for (i=0;i<p;i++) {
            if (nums[i]>nums[i+1]) {
                temp=nums[i];
                nums[i]=nums[i+1];
                nums[i+1]=temp;
                flag=1;
            }
        }
        if (flag==0) break;
    }
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
    if (!nums || numsSize<4) return 0;

    int total=100;
    int** res=(int**)malloc(sizeof(int*)*total);
    for (int n;n<total;n++) {
        res[n]=(int*)malloc(sizeof(int)*4);
    }

    Bubble_Sort(nums,numsSize);

    int size=0;
    int sum;
    int i,j,m,n;

    for (i=0;i<numsSize-3;i++) {
        if (i>0&&nums[i]==nums[i-1]) continue;

        for (j=i+1;j<numsSize-2;j++) {
            if (j>i+1&&nums[j]==nums[j-1]) continue;

            m=j+1;
            n=numsSize-1;

            while (m<n) {
                sum=nums[i]+nums[j]+nums[m]+nums[n];
                if (sum==target) {
                    if (size>0&&res[size-1][0]==nums[i]&&res[size-1][1]==nums[j]&&res[size-1][2]==nums[m]&&res[size-1][3]==nums[n]) {
                        m++;
                        n--;
                        continue;
                    }

                    if (size==total) {
                        res=(int**)realloc(res,sizeof(int*)*total);
                        for (int t=size;t<total;t++) {
                            res[t]=(int*)malloc(sizeof(int)*4);
                        }
                    }

                    res[size][0]=nums[i];
                    res[size][1]=nums[j];
                    res[size][2]=nums[m];
                    res[size][3]=nums[n];

                    size++;
                    m++;
                    n--;
                }
                else if (sum<target) {
                    m++;
                }
                else {
                    n--;
                }
            }
        }
    }

    *returnSize=size;
    return res;
}

/* Here we implement the quick sort algorithm. */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int *arr, int left, int right) {
    int pi = left;
    for (int i = left; i < right; ++i) {
        if (arr[i] <= arr[right])
            swap(&arr[pi++], &arr[i]);
    }
    swap(&arr[pi], &arr[right]);
    return pi;
}
void quick_sort(int *arr, int left, int right) {
    if (left >= right) return;
    int pi = partition(arr, left, right);
    quick_sort(arr, left, pi-1);
    quick_sort(arr, pi+1, right);
}

/* Here we implement the logic to double size a 2-D array. */
void check_size(int ***rets_ref, int *curr_size, int *max_size) {
    // we need to pass 2-D array as (int ***) to modify in place.
    if (*curr_size < *max_size) return;
    *max_size *= 2; // double size
    int **rets = malloc(sizeof(int *)*(*max_size));
    for (int i = 0; i < *curr_size; ++i) {
        rets[i] = (*rets_ref)[i];
    }
    int **tmp = *rets_ref;
    *rets_ref = rets;
    free(tmp);
}

/* Here we implement the 2-sum, 3-sum and 4-sum logic. */
void twoSum(int *nums, int numsSize, int target, int pi, int ***rets_ref, int *returnSize, int *size, int z1, int z2) {
    int **rets;
    int i = pi, j = numsSize-1, sum, x;
    while (i < j) {
        sum = nums[i] + nums[j];
        if (sum == target) {
            rets = *rets_ref; // may be resized during iteration
            rets[*returnSize] = malloc(sizeof(int)*4);
            rets[*returnSize][0] = z1;
            rets[*returnSize][1] = z2;
            rets[*returnSize][2] = nums[i];
            rets[*returnSize][3] = nums[j];
            (*returnSize)++;
            check_size(rets_ref, returnSize, size); // check and resize
            x = nums[i];
            while(++i < j && x == nums[i]); //avoid duplicate
            x = nums[j];
            while(--j > i && x == nums[j]); //avoid duplicate
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }
}
void threeSum(int *nums, int numsSize, int target, int pi, int ***rets_ref, int *returnSize, int *size, int z1) {
    int **rets;
    for (int i = pi; i < numsSize; ++i) {
        if (i >= numsSize-2)
            break; //no more
        if (i > pi && nums[i] == nums[i-1])
            continue; //avoid duplicate
        if (nums[i]+2*nums[numsSize-1] < target)
            continue; //too small
        if (3*nums[i] > target)
            break; //to large
        if (3*nums[i] == target) {
            rets = *rets_ref;
            if (i+2 < numsSize && nums[i+2] == nums[i]) {
                rets[*returnSize] = malloc(sizeof(int)*4);
                rets[*returnSize][0] = z1;
                for (int j = 0; j < 3; ++j)
                    rets[*returnSize][j+1] = nums[i+j];
                (*returnSize)++;
                check_size(rets_ref, returnSize, size); // check and resize
            }
            break;
        }
        twoSum(nums, numsSize, target-nums[i], i+1, rets_ref, returnSize, size, z1, nums[i]);
    }
}
int** fourSum(int *nums, int numsSize, int target, int *returnSize) {
    int **rets;
    int size = numsSize;
    rets = malloc(sizeof(int *)*size);
    *returnSize = 0;
    quick_sort(nums, 0, numsSize-1);
    for (int i = 0; i < numsSize; ++i) {
        if (i >= numsSize-3)
            break; //no more
        if (i && nums[i] == nums[i-1])
            continue; //skip duplicate
        if (nums[i]+3*nums[numsSize-1] < target)
            continue; //too small
        if (4*nums[i] > target)
            break; //to large
        if (4*nums[i] == target) {
            if (i+3 < numsSize && nums[i+3] == nums[i]) {
                rets[*returnSize] = malloc(sizeof(int)*4);
                for (int j = 0; j < 4; ++j)
                    rets[*returnSize][j] = nums[i+j];
                (*returnSize)++;
                check_size(&rets, returnSize, &size); // check and resize
            }
            break;
        }
        threeSum(nums, numsSize, target-nums[i], i+1, &rets, returnSize, &size, nums[i]);
    }
    return rets;
}

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
return *((int *)a)