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: Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d) The solution set must not contain duplicate quadruplets. For example, given …

LeetCode-4Sum

C++:
class Solution {
private:
    vector<vector<int>> ret;
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ret.clear();
        if(num.size()<4) return ret;
        sort(num.begin(),num.end());
        vector<int> cur(4);
        for(int i=0;i<num.size()-3;i++){
            for(int j=i+1;j<num.size()-2;j++){
                int k=j+1;
                int t=num.size()-1;
                while(k<t){
                    if(num[i]+num[j]+num[k]+num[t]<target) k++;
                    else if(num[i]+num[j]+num[k]+num[t]>target) t--;
                    else{
                        cur[0]=num[i];
                        cur[1]=num[j];
                        cur[2]=num[k];
                        cur[3]=num[t];
                        ret.push_back(cur);
                        k++;
                        t--;
                    }
                }
            } 
        }
        sort(ret.begin(),ret.end());
        ret.erase(unique(ret.begin(),ret.end()),ret.end());
        return ret;
    }
};
Java:
public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> ret=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> cur=new ArrayList<Integer>();
        if(num.length<4) return ret;
        Arrays.sort(num);
        for(int i=0;i<num.length-3;i++){
            for(int j=i+1;j<num.length-2;j++){
                int k=j+1;
                int t=num.length-1;
                while(k<t){
                    if(num[i]+num[j]+num[k]+num[t]<target) k++;
                    else if(num[i]+num[j]+num[k]+num[t]>target) t--;
                    else{
                        cur.add(num[i]);
                        cur.add(num[j]);
                        cur.add(num[k]);
                        cur.add(num[t]);
                        if(!ret.contains(cur)){ 
                            ArrayList<Integer> temp=new ArrayList<Integer>();
                            for(Integer it:cur) temp.add(it);
                            ret.add(temp);
                        } 
                        cur.clear();   
                        k++;
                        t--;
                    }
                }
            }
        }
        return ret;    
    }
}