題目：

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[  [-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]
思路：
采用循環(huán)或者遞歸，逐個查找計算總和。
代碼一（函數循環(huán)，12ms）
/** * 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) {    int flag;    int temp;    int min;    int **output=NULL;    int last1,last2,last3,last4;//用于記錄上一次取值    //用于判斷是否判斷此次取值與上次取值是否相同    int flag1=0;    int flag2=0;    int flag3=0;    int flag4=0;    int sizereturn=0;    //先進行排序    for(int i=0;i<numsSize;i++)    {        min=nums[i];        for(int j=i;j<numsSize;j++)        {            if(min>=nums[j])            {                flag=j;                min=nums[j];            }        }        temp=nums[flag];        nums[flag]=nums[i];        nums[i]=min;    }    for(int i=0;i<numsSize-3;i++)    {        if(flag1&&nums[i]==last1)continue;//改變第一個值時不可與前一個取值相同，否則重復        if(4*nums[i]>target)break;        if((nums[i]+nums[numsSize-1]+nums[numsSize-2]+nums[numsSize-3])<target)continue;        flag2=0;        for(int j=i+1;j<numsSize-2;j++)        {            if(flag2&&nums[j]==last2)continue;//改變第二個值時不可與前一個取值相同，否則重復            if((nums[i]+3*nums[j])>target)break;            //排序之后，最后的值最大，如果加上最后的值仍小于target，則跳過            if((nums[i]+nums[j]+nums[numsSize-2]+nums[numsSize-1])<target)continue;            flag3=0;            for(int k=j+1;k<numsSize-1;k++)            {                if(flag3&&nums[k]==last3)continue;//改變第三個值時不可與前一個取值相同，否則重復                if((nums[i]+nums[j]+nums[k]+nums[k])>target)break;                if((nums[i]+nums[j]+nums[k]+nums[numsSize-1])<target)continue;                flag4=0;                for(int m=k+1;m<numsSize;m++)                {                    if(flag4&&nums[m]==last4)continue;                    if(nums[i]+nums[j]+nums[k]+nums[m]==target)                    {                        sizereturn++;                        output=(int**)realloc(output,sizereturn*sizeof(int*));                        *(output+sizereturn-1)=(int*)malloc(4*sizeof(int));                        output[sizereturn-1][0]=nums[i];                        output[sizereturn-1][1]=nums[j];                        output[sizereturn-1][2]=nums[k];                        output[sizereturn-1][3]=nums[m];                    }                    else if((nums[i]+nums[j]+nums[k]+nums[m])>target)break;                    flag4=1;                    last4=nums[m];                }                flag3=1;                last3=nums[k];            }            flag2=1;            last2=nums[j];        }        flag1=1;        last1=nums[i];    }    *returnSize=sizereturn;    return output;}
代碼二（遞歸函數，19ms）
/** * Return an array of arrays of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */void findtarget(int* nums, int numsSize, int target,int output[],int index,int n,int ***returnarr,int *returnSize){    int flag=0;    int last;    if(n==1)    {        for(int i=index;i<numsSize-n+1;i++)        {            if(flag&&last==nums[i])continue;            if(-1*nums[i]+target==0)            {                (*returnSize)++;                output[n-1]=nums[i];                *returnarr=(int**)realloc(*returnarr,(*returnSize)*sizeof(int*));                *(*returnarr+(*returnSize)-1)=(int*)malloc(4*sizeof(int));                for(int j=0;j<4;j++)                {                    (*returnarr)[*returnSize-1][j]=output[3-j];                }            }            last=nums[i];            flag=1;        }    }    else    {        for(int i=index;i<numsSize-n+1;i++)        {            int sum=nums[i];            int sum2;            if(flag&&last==nums[i])continue;            output[n-1]=nums[i];            for(int si=numsSize-1;si>(numsSize-n);si--)                sum+=nums[si];            sum2=n*nums[i];            if(sum2>target)break;            if(sum<target)continue;            findtarget(nums,numsSize,target-nums[i],output,i+1,n-1,returnarr,returnSize);            last=nums[i];            flag=1;        }    }}int** fourSum(int* nums, int numsSize, int target, int* returnSize) {    int output[4];    int **returnarr=NULL;    int num=0;    int flag=0;    int last;    int min;    int minflag;    int temp;    *returnSize=0;    for(int i=0;i<numsSize;i++)    {        min=nums[i];        for(int j=i;j<numsSize;j++)        {            if(min>=nums[j])            {                minflag=j;                min=nums[j];            }        }        temp=nums[minflag];        nums[minflag]=nums[i];        nums[i]=min;    }    findtarget(nums,numsSize,target,output,0,4,&returnarr,returnSize);    return returnarr;}
思路拓展：
采用遞歸函數稍加修改可適用于K-SUM問題